北理工《数据结构与算法》在线作业满分答案

北理工《数据结构与算法》在线作业满分答案

北理工《数据结构与算法》在线作业

试卷总分:100 得分:100

一、单选题

1. 在数据结构中，与所使用的计算机无关的是数据的()结构

A. 逻辑

B. 存储

C. 逻辑和存储

D. 物理

正确答案:A

2.一个n*n对称矩阵，如果以行或列为主序存入内存，则其容量为()。

A. n*n

B. n*n/2

C. n*（n+1）/2

D. （n+1）*（n+1）/2

正确答案:C

3.一个数组第一个元素的存储地址是100，每个数组元素的长度为2，则第5个元素的地址是()。

A. 110

B. 108

C. 100

D. 120

正确答案:B

4.如果结点a有三个兄弟，而且b为a的双亲，则b的度为()。

A. 3

B. 4

C. 5

D. 2

正确答案:B

5. 下面四种内排序方法中，要求容量最大的是()。

A. 插入排序

B. 选择排序

C. 快速排序

D. 归并排序

正确答案:D

6. 采用顺序搜索方法查找长度为n的顺序表时，搜索成功的平均搜索长度为()。

A. n

B. n/2

C. （n-1）/2

D. （n+1）/2

正确答案:D

7. 图的存储结构不包括()

A. 数组表示

B. 邻接表

C. 邻接多重表

北京理工大学《数据结构》试题及答案(B卷)

一、单项选择题 1．算法必须具备的三个特性是( )。 A．可执行性、可移植性、可扩充性B．可执行性、确定性、有穷性 C．确定性、有穷性、稳定性D．易读性、稳定性、安全性 2．下列数据中，( )是非线性数据结构。 A．栈B．队列 C．完全二叉树D．顺序表 3．算法分析的两个方面是( )。 A．空间复杂度和时间复杂度B．正确性和简明性 C．可读性和文档性D．数据复杂性和程序复杂性 4．非空的循环单链表head的尾结点p满足( )。 A．p->next==head B．p->next==NULL C．p==NULL D．p==head 5．在单链表指针为p的结点之后插入指针为s的结点，正确的操作是( )。 A．p->next=s;s->next=p->next; B．s->next=p->next;p->next=s; C．p->next=s;p->next=s->next; D．p->next=s->next;p->next=s; 6．按照二叉树的定义，具有3个结点的二叉树有( )种。 A．3 B．4 C．5 D．6 7．在一个有向图中，所有顶点的入度之和是所有顶点的出度之和的( )倍。 A．1/2 B．1 C．2 D．4 8．二叉排序树是( )。 A．每一分支结点的度均为2的二叉树 B．中序遍历得到一升序序列的二叉树 C．按从左到右顺序编号的二叉树 D．每一分支结点的值均小于左子树上所有结点的值，大于右子树上所有结点的值9．若用一个大小为6的数组来实现循环队列，且当前rear和front的值分别为0和3，当从队列中删除一个元素，再加入两个元素后，rear和front的值分别是( )。 A．1和 5 B．2和4 C．4和2 D．5和1 10．下列说法中正确的是( )。 A．堆栈是在两端操作、先进后出的线性表 B．堆栈是在一端操作、先进先出的线性表 C．队列是在一端操作、先进先出的线性表 D．队列是在两端操作、先进先出的线性表

数据结构与算法习题及答案

第1章绪论 习题 1．简述下列概念：数据、数据元素、数据项、数据对象、数据结构、逻辑结构、存储结构、抽象数据类型。2．试举一个数据结构的例子，叙述其逻辑结构和存储结构两方面的含义和相互关系。 3．简述逻辑结构的四种基本关系并画出它们的关系图。 4．存储结构由哪两种基本的存储方法实现 5．选择题 （1）在数据结构中，从逻辑上可以把数据结构分成（）。 A．动态结构和静态结构B．紧凑结构和非紧凑结构 C．线性结构和非线性结构D．内部结构和外部结构 （2）与数据元素本身的形式、内容、相对位置、个数无关的是数据的（）。 A．存储结构B．存储实现 C．逻辑结构D．运算实现 （3）通常要求同一逻辑结构中的所有数据元素具有相同的特性，这意味着（）。 A．数据具有同一特点 B．不仅数据元素所包含的数据项的个数要相同，而且对应数据项的类型要一致 C．每个数据元素都一样 D．数据元素所包含的数据项的个数要相等 （4）以下说法正确的是（）。 A．数据元素是数据的最小单位 B．数据项是数据的基本单位 C．数据结构是带有结构的各数据项的集合 D．一些表面上很不相同的数据可以有相同的逻辑结构 （5）以下与数据的存储结构无关的术语是（）。 A．顺序队列B.链表C.有序表D.链栈 （6）以下数据结构中，（）是非线性数据结构 A．树B．字符串C．队D．栈 6．试分析下面各程序段的时间复杂度。 （1）x=90;y=100; while(y>0) if(x>100) {x=x-10;y--;} elsex++; （2）for(i=0;i

2022年北京理工大学计算机科学与技术专业《数据结构与算法》科目期末试卷A(有答案)

2022年北京理工大学计算机科学与技术专业《数据结构与算法》科目 期末试卷A（有答案） 一、选择题 1、下列说法不正确的是（）。 A.图的遍历是从给定的源点出发每个顶点仅被访问一次 B.遍历的基本方法有两种：深度遍历和广度遍历 C.图的深度遍历不适用于有向图 D.图的深度遍历是一个递归过程 2、下列排序算法中，占用辅助空间最多的是（）。 A.归并排序 B.快速排序 C.希尔排序 D.堆排序 3、线性表的顺序存储结构是一种（）。 A.随机存取的存储结构 B.顺序存取的存储结构 C.索引存取的存储结构 D.Hash存取的存储结构 4、已知有向图G=(V，E)，其中V={V1，V2，V3，V4，V5，V6，V7}， E=｛，，，，， ，，， ｝，G的拓扑序列是（）。 A.V1，V3，V4，V6，V2，V5，V7 B.V1，V3，V2，V6，V4，V5，V7 C.V1，V3，V5，V2，V6，V7 D.V1，V2，V5，V3，V4，V6，V7 5、用不带头结点的单链表存储队列，其队头指针指向队头结点，队尾指针指向队尾结点，则在进行出队操作时（）。 A.仅修改队头指针 B.仅修改队尾指针 C.队头、队尾指针都可能要修改 D.队头、队尾指针都要修改 6、下列关于无向连通图特性的叙述中，正确的是（）。

Ⅰ．所有的顶点的度之和为偶数Ⅱ．边数大于顶点个数减1 Ⅲ．至少有一个顶点的度为1 A．只有Ⅰ B．只有Ⅱ C．Ⅰ和Ⅱ D．Ⅰ和Ⅲ 7、排序过程中，对尚未确定最终位置的所有元素进行一遍处理称为一趟排序。下列排序 方法中，每一趟排序结束时都至少能够确定一个元素最终位置的方法是（）。 Ⅰ．简单选择排序Ⅱ．希尔排序Ⅲ．快速排序Ⅳ．堆排Ⅴ．二路归并排序 A．仅Ⅰ、Ⅲ、Ⅳ B．仅Ⅰ、Ⅱ、Ⅲ C．仅Ⅱ、Ⅲ、Ⅳ D．仅Ⅲ、Ⅳ、Ⅴ 8、一棵哈夫曼树共有215个结点，对其进行哈夫曼编码，共能得到（）个不同的码字。 A.107 B.108 C.214 D.215 9、每个结点的度或者为0或者为2的二叉树称为正则二叉树。n个结点的正则二叉树中 有（）个叶子。 A.log2n B.（n－1）/2 C.log2n+1 D.（n＋1）/2 10、下面关于B和B+树的叙述中，不正确的是（） A.B树和B+树都是平衡的多叉树 B.B树和B+树都可用于文件的索引结构 C.B树和B+树都能有效地支持顺序检索 D.B树和B+树都能有效地支持随机检索 二、填空题 11、对n个记录的表r[1..n]进行简单选择排序，所需进行的关键字间的比较次数为______。 12、有向图G=(V，E)，其中V(G)={0，1，2，3，4，5｝，用 三元组表示弧及弧上的权d。E(G)为E(G)=｛<0，5，100>，<0，2，10>，<1，2，5>，<0，4，30>，<4，5，60>，<3，5，10>，<2， 3，50>，<4，3，20>｝，则从源点0到顶点3的最短 路径长度是______，经过的中间顶点是______。 13、在单链表L中，指针P所指结点有后继结点的条件是______。 14、对于一个具有n个结点的单链表，在已知的结点半p后插入一个新结点的时间复杂 度为______，在给定值为x的结点后插入一个新结点的时间复杂度为______。 15、数据结构中评价算法的两个重要指标是______。 16、当两个栈共享一存储区时，栈利用一维数组stack（1，n）表示，两栈顶指针为top[1]与top[2]，则当栈1空时，top[1]为______，栈2空时， top[2]为______，栈满时为______。

北京理工大学数据结构试题及答案

北京理工大学数据结构 10 年期末试题 数据结构试卷(一) 、单选题(每题 2 分，共 20 分) 1. 栈和队列的共同特点是 ( ) A. 只允许在端点处插入和删除元素 B. 都是先进后出 C. 都是先进先出 D. 没有共同点 2. 用链接方式存储的队列，在进行插入运算时 ( ). A. 仅修改头指针 B. C. 仅修改尾指针 D. 3. 以下数据结构中哪一个是非线性结构？ A. 队列 B. 栈 C. 4. 设有一个二维数组 A [ m ][ n ] ，假设 A [0][0] 存放位置在 644(10) ，A [2][2] 存放位置在 676(10) ，每个元素占一个空间，问 A [3][3] (10) 存放在什么位置？脚注 (10) 表示用 10 进 制表示。 A ． 688 B ． 678 C 5. 树最适合用来表示 ( ) 。 A. 有序数据元素 B. 分查找，则查找 A: 3 ]的比较序列的下标依次为 () B. 9 ， 5， 2， 3 C. 9 ， 5， 3 D. 9 ， 4， 2， 3 8. 对 n 个记录的文件进行快速排序，所需要的辅助存储空间大致为 A. O (1) B. O ( n) C. O (1og 2n) D. O (n2) 9. 对于线性表( 7， 34， 55， 25， 64， 46， 20， 10)进行散列存储时，若选用 H(K) =K %9作为散列函数，则散列地址为 1 的元素有( )个， A ． 1 B ．2 C ．3 D ．4 10. 设有 6 个结点的无向图，该图至少应有 ( ) 条边才能确保是一个连通图。 A.5 B.6 C.7 D.8 二、填空题(每空 1分，共 26 分) 1. 通常从四个方面评价算法的质量： ____________ 、 ________ 、 __________ 和 __________ 。 3 2 2 2. 一个算法的时间复杂度为 ( n 3 +n log 2n +14n )/ n ，其数量级表示为 ________ 。 3. 假定一棵树的广义表表示为 A( C, D( E ，F, G ，H( I ，J)),则树中所含的结点数为 __________ 个，树的深度为 ___________ ，树的度为 __________ 。 4. 后缀算式 9 2 3 +- 10 2 / - 的值为 __________ 。中缀算式( 3+4X) -2Y/3 对应的后缀 算式为 __________________________________ 。 5. 若用链表存储一棵二叉树时, 每个结点除数据域外, 还有指向左孩子和右孩子的两个指 针。在这种存储结构中，n 个结点的二叉树共有 ____________ 个指针域，其中有 ________ 个 指针域是存放了地址,有 ___________________ 个指针是空指针。 6. 对于一个具有 n 个顶点和 e 条边的有向图和无向图, 在其对应的邻接表中, 所含边结点 分别有 ______ 个和 ________ 个。 7. AOV 网是一种 ____________________ 的图。 头、尾指针都要修改 头、尾指针可能都要修改 ( ) 线性表 D. 二叉树 692 D ．696 无序数据元素 C. 元素之间具有分支层次关系的数据 D. 元素之间无联系的数据 6. 二叉树的第 k 层的结点数最多为 ( ). k A ．2k -1 B.2K+1 C.2K-1 7. 若有 18 个元素的有序表存放在一维数组 D. 2 k-1 A[19] 中， 第一个元素放 A[1] 中，现进行二 A. 1 ， 2， 3

数据结构与算法在线作业答案

数据结构与算法在线作业答案

55283,单选题65512 1.邻接表是图的一种____。 A 顺序存储结构 B 链式存储结构 C 索引存储结构 D 散列存储结构 6550255281,单选题65502 2.具有5个顶点的有向完全图有____条弧。 A 10 B 16 C 20 D 25 6547555245,单选题65475 3.链表不具有的特点是_____。 A 可随机访问任一元素 B 插入和删除不需要移动元素 C 不必事先估计存储空间 D 所需空间和线性表长度成正比 6548555256,单选题65485 4.作进栈操作时，应先判断栈是否为_____。 A 空 B 满

C 上溢 D 下溢 6551555287,单选题65515 5.下面关于图的存储的叙述中，哪一个是正确的？ A 用相邻矩阵法存储图,占用的存储空间数只 与图中结点个数有关,而与边数无关 B 用相邻矩阵法存储图,占用的存储空间数只 与图中边数有关,而与结点个数无关 C 用邻接表法存储图，占用的存储空间数只与 图中结点个数有关，而与边数无关 D 用邻接表法存储图，占用的存储空间数只与 图中边数有关，而与结点个数无关6548655261,单选题65486 6.当字符序列 x5y 作为字符堆栈的输入时，输出长度为3的且可以作为C语言标识符的个数是____。 A 3个 B 4个 C 5个 D 6个 6547755253,单选题65477

7.树最适合用来表示_____。 A 有序数据元素 B 无序数据元素 C元素之间具有分支层次关系的数据 D 元素之间无联系的数据 6546055240,单选题65460 8.线性表按链式方式存储时，每个结点的存储包括_____两部分。 A 数据值与符号 B 数据与指针 C 数据与表名 D 数据项与符号 6549855268,单选题65498 9.树的基本遍历策略可分为先根遍历和后根遍历；二叉树的基本遍历策略可分为先序遍历、中序遍历和后序遍历。这里我们把由树转化得到的二叉树叫做这棵树对应的二叉树。那么以下结论中_____是正确的。 A 树的先根遍历序列与其对应的二叉树的先 序遍历序列相同 B 树的后根遍历序列与其对应的二叉树的后 序遍历序列相同

北理工《数据结构与算法》在线作业满分答案

北理工《数据结构与算法》在线作业 试卷总分:100 得分:100 一、单选题 1. 在数据结构中，与所使用的计算机无关的是数据的() 结构 A. 逻辑 B. 存储 C. 逻辑和存储 D. 物理正确答案:A 2. 一个n*n 对称矩阵，如果以行或列为主序存入内存，则其容量为() 。 A. n*n B. n*n/2 C. n* ( n+1) /2 D. (n+1)*( n+1) /2 正确答案:C 3. 一个数组第一个元素的存储地址是100，每个数组元素的长度为2，则第5 个元素的地址是() 。 A. 110 B. 108 C. 100 D. 120 正确答案:B 4. 如果结点a 有三个兄弟，而且b 为a 的双亲，则b 的度为() 。 A. 3 B. 4 C. 5 D. 2 正确答案:B 5. 下面四种内排序方法中，要求容量最大的是() 。 A. 插入排序 B. 选择排序 C. 快速排序 D. 归并排序正确答案:D 6. 采用顺序搜索方法查找长度为n 的顺序表时，搜索成功的平均搜索长度为() 。 A. n B. n/2 C. (n-1 )/2 D. ( n+1) /2 正确答案:D 7. 图的存储结构不包括() A. 数组表示 B. 邻接表 C. 邻接多重表 D. 孩子兄弟表示正确答案:D 8. 快速排序方法在() 情况下最不利于发挥其长处。 A. 被排序的数据量太大 B. 被排序数据中含有多个相同值

C. 被排序数据已基本有序 D. 被排序数据数目为奇数满分：2.5 分正确答案:C 9. 设数组Data[O..m]作为循环队列SQ的存储空间，front为队头指针，rear为队尾指针, 则执行出队操作的语句为() A. front=front+1 B. front=(front+1)% m C. rear=(rear+1)%m D. front=(front+1)%(m+1) 满分： 2.5 分 正确答案:D 10. 我们在讨论某种数据结构时，主要讨论四个方面的问题，①数据的逻辑结构②数据的存储结构 ③在数据的逻辑结构上定义的数据的基本操作；④基本操作算法的具体实现；这四个问题的讨论的先后顺序应该是怎样的？() A. ①②③④ B. ①③②④ C. ②①③④ D. ②①④③ 满分： 2.5 分 正确答案:B 11. 一个具有767 个结点的完全二叉树，其叶子结点个数为() 。 A. 383 B. 384 C. 385 D. 386 满分：2.5 分 正确答案:B 12. 栈与一般的线性表的区别在于() 。 A. 数据元素的类型不同 B. 运算是否受限制 C. 数据元素的个数不同 D. 逻辑结构不同满分：2.5 分 正确答案:B 13. 设连通图G 中的边集E={(a , b) , (a , e) , (a , c) , (b , e), (e , d) , (d , f) , (f , c)}, 则从顶点 a 出发可以得到一种深度优先遍历的顶点序列为()

北京理工大学数据结构作业（全）

北京理工大学数据结构作业（全） 北理工数据结构作业 第二章作业 1、在什么情况下用顺序表比链表好？（题集2.3） 需要对线性表进行随机存取时，顺序表比链表好。 2、已知L是带表头结点的非空单链表，且P结点既不是首元结点，也不是尾元结点，试从 下列提供的答案中选择合适的语句序列。（题集2.7） a.删除P结点的直接后继结点的语句序列是11 3 14。 b.删除P结点的直接前驱结点的语句序列是10 12 8 3 14。 c.删除P结点的语句序列是10 12 7 3 14。 d.删除首元结点的语句序列是12 11 3 14。 e.删除尾元结点的语句序列是12 11 3 14。 (1)p = p->next; (2)p->next = p; (3)p->next = p->next->next; (4)p = p->next->next; (5)while ( p!=NULL ) p=p->next; (6)while ( q->next!=NULL ) { p=q; q=q->next; } (7)while ( p->next!=q ) p=p->next; (8)while ( p->next->next!=q ) p=p->next; (9)while ( p->next->next!=NULL ) p=p->next; (10)q=p; (11)q=p->next; (12)p=l; (13)l=l->next; (14)free(q); 3、算法设计。设顺序表va中的数据元素递增有序，请设计一算法，将x插入到顺序表的

适当位置，以保持该表的有序性。（题集2.11） typedef struct{ ElemType *elem; int length; int listsize; }Sqlist; Status ListInsert_Sq(Sqlist &va , ElemType x){ if(va.length==va.listsize) return ERROR; for(i=va.length-1;i>=0&&x va.elem[i+1]=x; va.length++; return OK; } 4、算法设计。请设计一个算法，实现顺序表的原地逆置，即利用原表的存储空间将线性表 （a1，a2，……，an）逆置为（an，……，a2，a1）。（题集2.21） typedef struct{ ElemType *elem; int length; int listsize; }Sqlist; void ListReverse_Sq(Sqlist &L){ int i, j, x; for(i=0,j=L.length-1;i x=L.elem[j]; L.elem[j]=a.elem[i]; L.elem[i]=x;} } 5、算法设计。请设计一个算法，实现单链表的原地逆置。

北京理工大学数据结构试题及答案

理工大学数据结构10年期末试题 数据结构试卷〔一〕 一、单选题〔每题2 分,共20分〕 1.栈和队列的共同特点是< >. A.只允许在端点处插入和删除元素 B.都是先进后出 C.都是先进先出 D.没有共同点 2.用方式存储的队列,在进行插入运算时< >. A. 仅修改头指针 B. 头、尾指针都要修改 C. 仅修改尾指针 D.头、尾指针可能都要修改 3.以下数据结构中哪一个是非线性结构？< > A. 队列 B. 栈 C. 线性表 D. 二叉树 4.设有一个二维数组A[m][n],假设A[0][0]存放位置在644<10>,A[2][2]存放位置在676<10>, 每个元素占一个空间,问A[3][3]<10>存放在什么位置？脚注<10>表示用10进制表示. A．688 B．678 C．692 D．696 5.树最适合用来表示< >. A.有序数据元素 B.无序数据元素 C.元素之间具有分支层次关系的数据 D.元素之间无联系的数据 6.二叉树的第k层的结点数最多为< >. A．2k-1 B.2K+1 C.2K-1 D. 2k-1 7.若有18个元素的有序表存放在一维数组A[19]中,第一个元素放A[1]中,现进行二分查 找,则查找A［3］的比较序列的下标依次为< > A. 1,2,3 B. 9,5,2,3 C. 9,5,3 D. 9,4,2,3 8.对n个记录的文件进行快速排序,所需要的辅助存储空间大致为 A. O〔1〕 B. O〔n〕 C. O〔1og2n〕 D. O〔n2〕 9.对于线性表〔7,34,55,25,64,46,20,10〕进行散列存储时,若选用H〔K〕=K %9作为散 列函数,则散列地址为1的元素有〔〕个, A．1 B．2 C．3 D．4 10.设有6个结点的无向图,该图至少应有< >条边才能确保是一个连通图. A.5 B.6 C.7 D.8 二、填空题〔每空1分,共26分〕 1.通常从四个方面评价算法的质量：_________、_________、_________和_________. 2.一个算法的时间复杂度为/n2,其数量级表示为________. 3.假定一棵树的广义表表示为A〔C,D〔E,F,G〕,H〔I,J〕〕,则树中所含的结点数为__________ 个,树的深度为___________,树的度为_________. 4.后缀算式9 2 3 +- 10 2 / -的值为__________.中缀算式〔3+4X〕-2Y/3对应的后缀算式为 _______________________________. 5.若用链表存储一棵二叉树时,每个结点除数据域外,还有指向左孩子和右孩子的两个指针. 在这种存储结构中,n个结点的二叉树共有________个指针域,其中有________个指针域是存放了地址,有________________个指针是空指针. 6.对于一个具有n个顶点和e条边的有向图和无向图,在其对应的邻接表中,所含边结点分 别有_______个和________个.

北京理工大学数据结构试题及答案

北京理工大学数据结构试题及答案

北京理工大学数据结构10年期末试题 数据结构试卷（一） 一、单选题（每题2 分，共20分） 1.栈和队列的共同特点是( )。 A.只允许在端点处插入和删除元素 B.都是先进后出 C.都是先进先出 D.没有共同点 2.用链接方式存储的队列，在进行插入运算时 ( ). A. 仅修改头指针 B. 头、尾指针都要修改 C. 仅修改尾指针 D.头、尾指针可能都要修改 3.以下数据结构中哪一个是非线性结构？ ( ) A. 队列 B. 栈 C. 线性表 D. 二叉树 4.设有一个二维数组A[m][n]，假设A[0][0]存放 位置在644(10)，A[2][2]存放位置在676(10)，每个元素占一个空间，问A[3][3](10)存放在什么位置？脚注(10)表示用10进制表示。

A．688 B．678 C．692 D．696 5.树最适合用来表示( )。 A.有序数据元素 B.无序数据元素 C.元素之间具有分支层次关系的数据 D.元素之间无联系的数据 6.二叉树的第k层的结点数最多为( ). A．2k-1 B.2K+1 C.2K-1 D. 2k-1 7.若有18个元素的有序表存放在一维数组 A[19]中，第一个元素放A[1]中，现进行二分查找，则查找A［3］的比较序列的下标依次为( ) A. 1，2，3 B. 9，5，2，3 C. 9，5，3 D. 9，4，2，3 8.对n个记录的文件进行快速排序，所需要的 辅助存储空间大致为 A. O（1） B. O（n） C. O （1og2n） D. O（n2） 9.对于线性表（7，34，55，25，64，46，20， 10）进行散列存储时，若选用H（K）=K %9作为散列函数，则散列地址为1的元素有

算法与数据结构试题及答案

数据结构模拟试题... 一、简答题15分,每小题3分 1.简要说明算法与程序的区别; 2.在哈希表中,发生冲突的可能性与哪些因素有关为什么 3. 4.说明在图的遍历中,设置访问标志数组的作用; 5.说明以下三个概念的关系：头指针,头结点,首元素结点; 6.在一般的顺序队列中,什么是假溢出怎样解决假溢出问题 7. 二、判断题10分,每小题1分 正确在括号内打√,错误打× 1广义表 a , b, c 的表头是 a , b,表尾是 c ; 2在哈夫曼树中,权值最小的结点离根结点最近; 3基数排序是高位优先排序法; 4在平衡二叉树中,任意结点左右子树的高度差绝对值不超过1; 5在单链表中,给定任一结点的地址p,则可用下述语句将新结点s插入结点p的后面：p->next = s; s->next = p->next; 6抽象数据类型ADT包括定义和实现两方面,其中定义是独立于实现的,定义仅给出一个ADT的逻辑特性,不必考虑如何在计算机中实现; 7数组元素的下标值越大,存取时间越长; 8用邻接矩阵法存储一个图时,在不考虑压缩存储的情况下,所占用的存储空间大小只与图中结点个数有关,而与图的边数无关; 9拓扑排序是按AOE网中每个结点事件的最早发生时间对结点进行排序; 10长度为1的串等价于一个字符型常量; 三、单项选择题10分, 每小题1分 1．排序时扫描待排序记录序列,顺次比较相邻的两个元素的大小,逆序时就交换位置;这是哪种排序方法的基本思想 A、堆排序 B、直接插入排序 C、快速排序 D、冒泡排序 2．已知一个有向图的邻接矩阵表示,要删除所有从第i个结点发出的边,应该： A将邻接矩阵的第i行删除 B将邻接矩阵的第i行元素全部置为0 C将邻接矩阵的第i列删除 D将邻接矩阵的第i列元素全部置为0 3．有一个含头结点的双向循环链表,头指针为head, 则其为空的条件是： A. head->priro==NULL B. head->next==NULL C. head->next==head D. head->next-> priro==NULL 4. 在顺序表 3, 6, 8, 10, 12, 15, 16, 18, 21, 25, 30 中,用折半法查找关键码值11,所需的关键码比较次数为： A 2 B 3 C 4 D 5 5. 以下哪一个不是队列的基本运算 A从队尾插入一个新元素 B从队列中删除第i个元素 C判断一个队列是否为空 D读取队头元素的值 6. 在长度为n的顺序表的第i个位置上插入一个元素1≤ i ≤n+1,元素的移动次数为： A n – i + 1 B n – i C i D i – 1 7．对于只在表的首、尾两端进行插入操作的线性表,宜采用的存储结构为: A 顺序表 B 用头指针表示的循环单链表

数据结构与算法 试题及答案

绪论 一、填空题 1、数据的逻辑结构是数据元素之间的逻辑关系，通常有下列4类：集合＿、线性结构＿、树型结构＿、图状结构＿。 2、数据的存储结构是数据在计算机存储器里的表示，主要有4种基本存储方法：顺序存储＿、链式存储＿、索引存储＿、散列存储＿。 二、选择题 1、一个算法必须在执行有穷步之后结束，这是算法的（B ）。 A、正确性 B、有穷性 C、确定性 D、可行性 2、算法的每一步必须有确切的定义，也就是说，对于每步需要执行的动作必须严格、清楚地给出规定，这是算法的（A）。 A、正确性 B、有穷性 C、确定性 D、可行性 3、算法原则上都是能够有机器或人所完成的。整个算法好象是一个解决问题的“工作序列”，其中的每一步都是我们力所能及的一个动作，这是算法的（D） A、正确性 B、有穷性 C、确定性 D、可行性 三、简单题 1、什么是数据结构？什么是算法？两者有什么关系？ 什么是数据结构？数据结构是按某种逻辑关系组织起来的一批数据（或称带结构的数据元素的集合）应用计算机语言并按一定的存储表示方式把它们存储在计算机的存储器中，并在其上定义了一个运算的集合。 什么是算法？广义地说,为解决一个问题而采取的方法和步骤,就称为“算法” 两者有什么关系？算法与数据结构关系密切。选择的数据结构是否恰当直接影响算法的效率；而数据结构的优劣由算法的执行来体现。 2、什么是复杂度和空间复杂度？ 时间复杂度是指执行算法所需要的计算工作量；而 空间复杂度是指执行这个算法所需要的内存空间。 3、数据的逻辑结构分几种？存储结构又有哪几种？ 数据的逻辑结构：结构定义中的“关系”，描述的是数据元素之间的逻辑关系；包括线性结构（线性表、栈、队、串、数组）和非线性结构（图形结构、树形结构）； 数据的存储结构（物理结构）：数据结构在计算机中的表示（又称映像），包括数据元素的表示和关系德表示。有顺序存贮（向量存贮）、链式存贮、索引存贮、散列存贮。 线性表 1、一个线性表第一个元素的存储地址是100，每个元素的长度 为2，则第5 个元素的地址是( B)。 （A）110 （B）108（C）100 （D）120 2、向一个有127 个元素的顺序表中插入一个新元素并保持原来 顺序不变，平均要移动（C）个元素。 （A）64（B）63 （C）63.5（D）7 2、线性表采用链式存储结构时，其地址( D)。 (A) 必须是连续的(B) 部分地址必须是连续的

2022年北京大学计算机科学与技术专业《数据结构与算法》科目期末试卷A(有答案)

2022年北京大学计算机科学与技术专业《数据结构与算法》科目期末 试卷A（有答案） 一、选择题 1、从未排序序列中依次取出一个元素与已排序序列中的元素依次进行比较，然后将其放 在已排序序列的合适位置，该排序方法称为（）排序法。 A.插入 B.选择 C.希尔 D.二路归并 2、下列排序算法中，占用辅助空间最多的是（）。 A.归并排序 B.快速排序 C.希尔排序 D.堆排序 3、计算机算法指的是解决问题的步骤序列，它必须具备（）三个特性。 A.可执行性、可移植性、可扩充性 B.可执行性、确定性、有穷性 C.确定性、有穷性、稳定性 D.易读性、稳定性、安全性 4、用不带头结点的单链表存储队列，其队头指针指向队头结点，队尾指针指向队尾结点，则在进行出队操作时（）。 A.仅修改队头指针 B.仅修改队尾指针 C.队头、队尾指针都可能要修改 D.队头、队尾指针都要修改 5、下列关于AOE网的叙述中，不正确的是（）。 A.关键活动不按期完成就会影响整个工程的完成时间 B.任何一个关键活动提前完成，那么整个工程将会提前完成 C.所有的关键活动提前完成，那么整个工程将会提前完成 D.某些关键活动若提前完成，那么整个工程将会提前完成 6、下列叙述中，不符合m阶B树定义要求的是（）。

A．根结点最多有m棵子树 B．所有叶结点都在同一层上 C．各结点内关键字均升序或降序排列 D．叶结点之间通过指针链接 7、排序过程中，对尚未确定最终位置的所有元素进行一遍处理称为一趟排序。下列排序方法中，每一趟排序结束时都至少能够确定一个元素最终位置的方法是（）。 Ⅰ．简单选择排序Ⅱ．希尔排序Ⅲ．快速排序Ⅳ．堆排Ⅴ．二路归并排序 A．仅Ⅰ、Ⅲ、Ⅳ B．仅Ⅰ、Ⅱ、Ⅲ C．仅Ⅱ、Ⅲ、Ⅳ D．仅Ⅲ、Ⅳ、Ⅴ 8、一个具有1025个结点的二叉树的高h为（）。 A.11 B.10 C.11至1025之间 D.10至1024之间 9、有n（n>0）个分支结点的满二叉树的深度是（）。 A.n2-1 B.log2（n+1）+1 C.log2（n+1） D.log2（n-l） 10、在平衡二叉树中插入一个结点后造成了不平衡，设最低的不平衡结点为A，并已知A 的左孩子的平衡因子为0，右孩子的平衡因子为l，则应作（）型调整以使其平衡 A.LL B.LR C.RL D.RR 二、填空题 11、N个顶点的连通图用邻接矩阵表示时，该矩阵至少有______个非零元素。 12、在有n个顶点的有向图中，每个顶点的度最大可达______。 13、按LSD进行关键字排序，除最次位关键字之外，对每个关键字进行排序时，只能用______的排序方法。 14、已知有序表为（12，18，24，35，47，50，62，83，90，115， 134）当用二分法查找90时，需______次查找成功，查找47时______成功，查找100时，需______次才能确定不成功。 15、数据结构中评价算法的两个重要指标是______。 16、在顺序存储的二叉树中，编号为i和j的两个结点处在同一层的条件是______。

2022年北京工业大学计算机科学与技术专业《数据结构与算法》科目期末试卷A(有答案)

2022年北京工业大学计算机科学与技术专业《数据结构与算法》科目 期末试卷A（有答案） 一、选择题 1、用有向无环图描述表达式(A+B)*((A+B)／/A)，至少需要顶点的数目为（）。 A.5 B.6 C.8 D.9 2、设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主存储， a11为第一元素，其存储地址为1，每个元素占一个地址空间，则a85的地址为（）。 A.13 B.33 C.18 D.40 3、连续存储设计时，存储单元的地址（）。 A.一定连续 B.一定不连续 C.不一定连续 D.部分连续，部分不连续 4、在下列表述中，正确的是（） A.含有一个或多个空格字符的串称为空格串 B.对n（n>0）个顶点的网，求出权最小的n-1条边便可构成其最小生成树 C.选择排序算法是不稳定的 D.平衡二叉树的左右子树的结点数之差的绝对值不超过l 5、已知串S='aaab'，其next数组值为（）。 A.0123 B.1123 C.1231 D.1211 6、循环队列放在一维数组A中，end1指向队头元素，end2指向队尾元素的后一个位置。假设队列两端均可进行入队和出队操作，队列中最多能容纳M－1个元素。初始时为空， 下列判断队空和队满的条件中，正确的是（）。 A．队空：end1＝＝end2；队满：end1＝＝（end2＋1）mod M B．队空：end1＝＝end2；队满：end2＝＝（end1＋1）mod （M－1） C．队空：end2＝＝（end1＋1）mod M；队满：end1＝＝（end2＋1） mod M D．队空：end1＝＝（end2＋1）mod M；队满：end2＝＝（end1＋1） mod （M－1）

2022年华北理工大学计算机科学与技术专业《数据结构与算法》科目期末试卷A(有答案)

2022年华北理工大学计算机科学与技术专业《数据结构与算法》科目 期末试卷A（有答案） 一、选择题 1、若需在O（nlog2n）的时间内完成对数组的排序，且要求排序是稳定的，则可选择的排序方法是（）。 A.快速排序 B.堆排序 C.归并排序 D.直接插入排序 2、下列排序算法中，占用辅助空间最多的是（）。 A.归并排序 B.快速排序 C.希尔排序 D.堆排序 3、以下数据结构中，（）是非线性数据结构。 A.树 B.字符串 C.队 D.栈 4、动态存储管理系统中，通常可有（）种不同的分配策略。 A.1 B.2 C.3 D.4 5、已知有向图G=(V，E)，其中V={V1，V2，V3，V4，V5，V6，V7}， E=｛，，，，， ，，，｝，G的拓扑序列是（）。 A.V1，V3，V4，V6，V2，V5，V7 B.V1，V3，V2，V6，V4，V5，V7 C.V1，V3，V5，V2，V6，V7 D.V1，V2，V5，V3，V4，V6，V7 6、下列选项中，不能构成折半查找中关键字比较序列的是（）。 A．500，200，450，180 B．500，450，200，180 C．180，500，200，450 D．180，200，500，450 7、下列关于无向连通图特性的叙述中，正确的是（）。 Ⅰ．所有的顶点的度之和为偶数Ⅱ．边数大于顶点个数减1 Ⅲ．至少有一个顶点的度为1 A．只有Ⅰ B．只有Ⅱ C．Ⅰ和Ⅱ D．Ⅰ和Ⅲ 8、一棵非空的二叉树的前序序列和后序序列正好相反，则该二叉树一定满足（）。 A.其中任意一个结点均无左孩子

数据结构与算法复习题库含答案

数据结构复习题 第一章概论 一、选择题 1、研究数据结构就是研究( D )。 A. 数据的逻辑结构 B. 数据的存储结构 C. 数据的逻辑结构和存储结构 D. 数据的逻辑结构、存储结构及其基本操作 2、算法分析的两个主要方面是( A )。 A. 空间复杂度和时间复杂度 B. 正确性和简单性C. 可读性和文档性 D. 数据复杂性和程序复杂性 3、具有线性结构的数据结构是( D )。 A. 图 B. 树 C. 广义表 D. 栈 4、计算机中的算法指的是解决某一个问题的有限运算序列,它必须具备输入、输出、( B )等5个特性。 A. 可执行性、可移植性和可扩充性 B. 可执行性、有穷性和确定性 C. 确定性、有穷性和稳定性 D. 易读性、稳定性和确定性 5、下面程序段的时间复杂度是( C )。 fori0;im;i++ forj0;jn;j++ a[i][j]i*j; A. Om2 B. On2 C. Om*n D. Om+n 6、算法是( D )。

A. 计算机程序 B. 解决问题的计算方法 C. 排序算法 D. 解决问题的有限运算序列 7、某算法的语句执行频度为(3n+nlog2n+n2+8),其时间复杂度表示( C )。 A. On B. Onlog2n C. On2 D. Olog2n 8、下面程序段的时间复杂度为( C )。 i1; whilein ii*3; A. On B. O3n C. Olog3n D. On3 9、数据结构是一门研究非数值计算的程序设计问题中计算机的数据元素以及它们之间的( B )和运算等的学科。 A. 结构 B. 关系 C. 运算 D. 算法 10、下面程序段的时间复杂度是( A )。 is0; whilesn i++;s+i; A. On B. On2 C. Olog2n D. On3 11、抽象数据类型的三个组成部分分别为( A )。 A. 数据对象、数据关系和基本操作 B. 数据元素、逻辑结构和存储结构 C. 数据项、数据元素和数据类型 D. 数据元素、数据结构和数据类型 12、通常从正确性、易读性、健壮性、高效性等4个方面评价算法的质量,以下解释错误的是(D)。

算法与数据结构试题及答案

数据结构试卷（一） 一、单选题（每题2 分，共20分） 1.栈和队列的共同特点是( )。 A.只允许在端点处插入和删除元素 B.都是先进后出 C.都是先进先出 D.没有共同点 2.用链接方式存储的队列，在进行插入运算时( ). A. 仅修改头指针 B. 头、尾指针都要修改 C. 仅修改尾指针 D.头、尾指针可能都要修改 3.以下数据结构中哪一个是非线性结构？( ) A. 队列 B. 栈 C. 线性表 D. 二叉树 4.设有一个二维数组A[m][n]，假设A[0][0]存放位置在644(10)，A[2][2]存放位置在 676(10)，每个元素占一个空间，问A[3][3](10)存放在什么位置？脚注(10)表示用10进制表示。 A．688 B．678 C．692 D．696 5.树最适合用来表示( )。 A.有序数据元素 B.无序数据元素 C.元素之间具有分支层次关系的数据 D.元素之间无联系的数据 6.二叉树的第k层的结点数最多为( ). A．2k-1 B.2K+1 C.2K-1 D. 2k-1 7.若有18个元素的有序表存放在一维数组A[19]中，第一个元素放A[1]中，现进行二 分查找，则查找A［3］的比较序列的下标依次为( ) A. 1，2，3 B. 9，5，2，3 C. 9，5，3 D. 9，4，2，3 8.对n个记录的文件进行快速排序，所需要的辅助存储空间大致为 A. O（1） B. O（n） C. O（1og2n） D. O（n2） 9.对于线性表（7，34，55，25，64，46，20，10）进行散列存储时，若选用H（K） =K %9作为散列函数，则散列地址为1的元素有（）个， A．1 B．2 C．3 D．4 10.设有6个结点的无向图，该图至少应有( )条边才能确保是一个连通图。 A.5 B.6 C.7 D.8 二、填空题（每空1分，共26分） 1.通常从四个方面评价算法的质量：_________、_________、_________和_________。 2.一个算法的时间复杂度为(n3+n2log2n+14n)/n2，其数量级表示为________。 3.假定一棵树的广义表表示为A（C，D（E，F，G），H（I，J）），则树中所含的结点数 为__________个，树的深度为___________，树的度为_________。 4.后缀算式9 2 3 +- 10 2 / -的值为__________。中缀算式（3+4X）-2Y/3对应的后缀算式 为_______________________________。 5.若用链表存储一棵二叉树时，每个结点除数据域外，还有指向左孩子和右孩子的两个指 针。在这种存储结构中，n个结点的二叉树共有________个指针域，其中有________个指针域是存放了地址，有________________个指针是空指针。 6.对于一个具有n个顶点和e条边的有向图和无向图，在其对应的邻接表中，所含边结点 分别有_______个和________个。 7.AOV网是一种___________________的图。 8.在一个具有n个顶点的无向完全图中，包含有________条边，在一个具有n个顶点的有 向完全图中，包含有________条边。 9.假定一个线性表为(12,23,74,55,63,40)，若按Key % 4条件进行划分，使得同一余数的元 素成为一个子表，则得到的四个子表分别为____________________________、___________________、_______________________和__________________________。