数据结构试卷03答案

数据结构期末试卷及答案3⼀、单项选择题（本⼤题共15⼩题，第⼩题2分，共30分）在每⼩题列出的四个选项中只有⼀个符合题⽬要求，请将其代码填在题后的括号内。

错选或未选均⽆分。

1. 算法必须具备输⼊、输出和[ C ]A. 计算⽅法B. 排序⽅法C．解决问题的有限运算步骤 D. 程序设计⽅法2. 有n个节点的顺序表中，算法的时间复杂度是O(1)的操作是[ A ]A.访问第i个节点（1≤i≤n）B.在第i个节点后插⼊⼀个新节点（1≤i≤n）C.删除第i个节点（1≤i≤n）D.将n个节点从⼩到⼤排序3．单链表的存储密度[ C] A．⼤于1 B. 等于1C．⼩于1 D. 不能确定4．设将整数1,2,3,4,5依次进栈，最后都出栈，出栈可以在任何时刻（只要栈不空）进⾏，则出栈序列不可能是[ B] A．23415 B. 54132C．23145 D. 154325. 循环队列SQ的存储空间是数组d[m]，队头、队尾指针分别是front和rear，则执⾏出队后其头指针front值是[ D ]A．front=front+1 B. front=(front+1)%(m-1)C. front=(front-1)%mD. front=(front+1)%m6. 在⼀个具有n个结点的有序单链表中插⼊⼀个新结点并仍然保持有序的时间复杂度是[ B ]A. O(1)B. O(n)C. O(n2)D. O(nlogn)7. 设⼆维数组A[0..m-1][0..n-1]按⾏优先顺序存储，则元素A[i][j]的地址为[ B ] A．LOC(A[0][0])+(i*m+j) B．LOC(A[0][0])+(i*n+j)C.LOC(A[0][0])+[(i-1)*n+j-1]D. LOC(A[0][0])+[(i-1)*m+j-1]8. ⼀个⾮空⼴义表的表头[ D ]A．⼀定是⼦表 B. ⼀定是原⼦C．不能是⼦表 D. 可以是原⼦，也可以是⼦表9．具有n个节点的完全⼆叉树的深度为[ A ] A．?log2(n+1)? -1 B. log2n+1C. log2nD. ?log2n?10. 若要惟⼀地确定⼀棵⼆叉树，只需知道该⼆叉树的[ D ]A．前序序列 B. 中序序列C．前序和后序序列 D. 中序和后序序列11．在⼀个⽆向图中，所有顶点的度数之和等于图的边数的倍[ C ] A．1/2 B. 1C. 2D. 412. 拓扑排序运算只能⽤于[ C ]A．带权有向图 B. 连通⽆向图C．有向⽆环图 D. ⽆向图13．在所有排序⽅法中，关键字⽐较的次数与记录的初始排列次序⽆关的是[ D ] A．希尔排序 B. 冒泡排序C．插⼊排序 D. 选择排序14．下列排序算法中时间复杂度不受数据初始状态影响，恒为O(n2)的是[ C ] A．堆排序 B. 冒泡排序C．直接选择排序 D. 快速排序15．⼆分查找要求节点[ A ] A．有序、顺序存储 B. 有序、链接存储C．⽆序、顺序存储 D. ⽆序、链接存储⼆、填空题（本⼤题共10⼩题，每⼩题2分，共20分）不写解答过程，将正确的答案写在每⼩题的空格内。

数据结构试卷（一）一、选择题(20分）1．组成数据的基本单位是（ 1。

C ）。

(A) 数据项（B) 数据类型（C) 数据元素(D）数据变量2．设数据结构A=(D，R)，其中D=｛1,2，3，4}，R=｛r｝，r={〈1，2>,<2，3>，〈3，4>，〈4，1〉}，则数据结构A是( C )。

（A）线性结构(B）树型结构(C）图型结构(D) 集合3．数组的逻辑结构不同于下列（D）的逻辑结构.（A）线性表（B）栈(C) 队列（D) 树4．二叉树中第i(i≥1)层上的结点数最多有（C）个。

（A） 2i （B） 2i（C） 2i—1(D) 2i-15．设指针变量p指向单链表结点A，则删除结点A的后继结点B需要的操作为（。

A ）.(A）p-〉next=p-〉next->next （B) p=p—〉next(C) p=p->next—>next （D）p->next=p6．设栈S和队列Q的初始状态为空,元素E1、E2、E3、E4、E5和E6依次通过栈S，一个元素出栈后即进入队列Q，若6个元素出列的顺序为E2、E4、E3、E6、E5和E1,则栈S的容量至少应该是（.C ）。

(A） 6 （B） 4 (C) 3 （D) 27．将10阶对称矩阵压缩存储到一维数组A中,则数组A的长度最少为（C ）.（A） 100 (B） 40 (C) 55 （D） 808．设结点A有3个兄弟结点且结点B为结点A的双亲结点，则结点B的度数数为(8。

B(A) 3 (B) 4 (C） 5 (D） 19．根据二叉树的定义可知二叉树共有（ B）种不同的形态.(A） 4 （B) 5 (C) 6 （D) 710.设有以下四种排序方法,则( B ）的空间复杂度最大。

(A）冒泡排序（B）快速排序(C) 堆排序（D) 希尔排序二、填空题（30分)1.设顺序循环队列Q［0：m—1］的队头指针和队尾指针分别为F和R，其中队头指针F指向当前队头元素的前一个位置，队尾指针R指向当前队尾元素所在的位置，则出队列的语句为 F =____________；。

《数据结构》期末考试试卷试题及答案第一部分：选择题（每题2分，共20分）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. 堆7. 下面哪个数据结构用于实现最小树算法？A. 栈B. 队列C. 散列表D. 堆8. 下面哪个数据结构用于实现拓扑排序算法？A. 栈B. 队列C. 散列表D. 堆9. 下面哪个数据结构用于实现最短路径算法？A. 栈B. 队列C. 散列表D. 堆10. 下面哪个数据结构用于实现并查集算法？A. 栈B. 队列C. 散列表D. 堆第二部分：填空题（每题2分，共20分）1. 链表是一种______数据结构。

2. 二叉树的节点最多有______个子节点。

3. 堆是一种特殊的______。

4. 散列表的查找效率取决于______。

5. 图的遍历算法包括______和______。

6. 快速排序算法的平均时间复杂度为______。

7. 哈希表中的冲突解决方法有______和______。

8. 最小树算法包括______和______。

9. 最短路径算法包括______和______。

10. 并查集算法用于解决______问题。

第三部分：简答题（每题10分，共50分）1. 请简述栈和队列的区别。

2. 请简述二叉搜索树的特点。

3. 请简述哈希表的原理。

4. 请简述图的深度优先搜索算法。

5. 请简述最小树算法的原理。

第四部分：编程题（每题20分，共50分）1. 编写一个函数，实现链表的插入操作。

数据结构第三单元测验答案数据结构第三次单元测验答案⼀、选择题1.对N个元素的表做顺序查找时，若查找每个元素的概率相同，则平均查找长度为( ) A．（N+1）/2 B. N/2 C. N D.[（1+N）*N ]/22.适⽤于折半查找的表的存储⽅式及元素排列要求为( )A．链接⽅式存储，元素⽆序 B．链接⽅式存储，元素有序C．顺序⽅式存储，元素⽆序D．顺序⽅式存储，元素有序3.当在⼀个有序的顺序存储表上查找⼀个数据时，即可⽤折半查找，也可⽤顺序查找，但前者⽐后者的查找速度( )A．必定快 B.不⼀定 C. 在⼤部分情况下要快 D. 取决于表递增还是递减4．有⼀个长度为12的有序表，按⼆分查找法对该表进⾏查找，在表内各元素等概率情况下查找成功所需的平均⽐较次数为（）。

A．35/12 B.37/12 C.39/12 D.43/125.折半查找的时间复杂性为（）A. O（n2）B. O（n）C. O（nlogn）D. O（logn）6.对有18个元素的有序表作折半查找，则查找A[3]的⽐较序列的下标为（）A.1，2，3B.9，5，2，3C.9，5，3D.9，4，2，37.设有序表的关键字序列为{1，4，6，10，18，35，42，53，67，71，78，84，92，99}，当⽤⼆分查找法查找健值为84的结点时，经（）次⽐较后查找成功。

A.2B. 3C. 4D.128.⽤n个键值构造⼀棵⼆叉排序树，最低⾼度为（）A.n/2B.、nC.lognD.logn+19．分别以下列序列构造⼆叉排序树，与⽤其它三个序列所构造的结果不同的是( ) A．（100，80， 90， 60，120，110，130）B.（100，120，110，130，80， 60， 90）C.（100，60， 80， 90， 120，110，130）D.(100，80， 60， 90， 120，130，110)10.设有⼀组记录的关键字为{19，14，23，1，68，20，84，27，55，11，10，79}，⽤链地址法构造散列表，散列函数为H（key）=key% 13,散列地址为1的链中有（）个记录。

数据结构试卷试题及答案一、选择题（每题5分，共40分）1. 数据结构是研究数据元素的（）A. 存储结构B. 处理方法C. 逻辑结构D. 所有以上内容答案：D2. 在数据结构中，通常采用（）方式来表示数据元素之间的逻辑关系。

A. 顺序存储结构B. 链式存储结构C. 索引存储结构D. 散列存储结构答案：B3. 下面哪一个不是栈的基本操作？（）A. 入栈B. 出栈C. 判断栈空D. 获取栈顶元素答案：D4. 下面哪一个不是队列的基本操作？（）A. 入队B. 出队C. 判断队列空D. 获取队头元素答案：D5. 下面哪一个不是线性表的特点？（）A. 有且只有一个根节点B. 每个节点最多有一个前驱和一个后继C. 数据元素类型相同D. 数据元素类型可以不同答案：D6. 在下列哪种情况中，使用链式存储结构比顺序存储结构更合适？（）A. 数据元素经常插入和删除B. 数据元素大小不固定C. 数据元素个数不确定D. 所有以上情况答案：D7. 下面哪一个不是树的遍历方式？（）A. 前序遍历B. 中序遍历C. 后序遍历D. 翻转遍历答案：D8. 在下列哪种情况中，使用散列存储结构比其他存储结构更合适？（）A. 数据元素个数较少B. 数据元素查找频繁C. 数据元素插入和删除频繁D. 数据元素大小不固定答案：B二、填空题（每题5分，共30分）9. 栈是一种特殊的线性表，它的插入和删除操作都限定在表的一端进行，这一端称为______。

答案：栈顶10. 队列是一种特殊的线性表，它的插入操作在表的一端进行，这一端称为______，而删除操作在另一端进行，这一端称为______。

答案：队尾、队头11. 二叉树中的节点包括______和______。

答案：根节点、子节点12. 在图的存储结构中，邻接矩阵表示法用______个一维数组来表示图中各个顶点之间的关系。

答案：两个13. 散列存储结构中，关键码到存储地址的映射方法称为______。

数据结构试题3参考答案一、单项选择题（本大题共15小题，每小题2分，共30分） 1．Ｄ ２．Ｂ３．Ｃ４．Ｂ５．Ｄ６．Ａ ７．Ｃ８，Ｄ９，Ａ10．Ｃ11．Ｄ 12．Ｃ13．Ｄ 14．Ｃ15．Ｂ二、填空题（本大题共10小题，每小题2分，共20分） 16．存储（或存储结构）17.p －＞next －＞next18．进栈和退栈．进栈和退栈19．12 12 2020．A[4][8] 21．384 22．abefcdg 23．快速排序、堆排序、希尔排序24．２．２ 25.多关键字多关键字三、解答题（本大题共4小题，每小题5分，共20分） 26．（1）对第一结点的操作和其他结点一样，无须特殊处理。

（（2）空表和非空表的处理相统一了。

）空表和非空表的处理相统一了。

27．28．该图的图形为：该图的图形为：深度优先遍历序列为：深度优先遍历序列为：abdce abdce广度优先遍历序列为：广度优先遍历序列为：abedc abedc2929．．（１）对关键字3535、、2020、、33和48进行查找的比较次数为３、２、１、１；１、１；（２）平均查找长度（２）平均查找长度59521123=++++=ASL四、算法阅读题（本大题共4小题，每小题5分，共20分） 30． ①S1=S1－>next ②s2=s2－>next ③s2(或s2!=NULL 或s2&&!s1) ④s1(或s1!=NULL 或s1&&!s2) ⑤return 0 31.（1）查询链表的尾结点）查询链表的尾结点（2）将第一个结点链接到链表的尾部，作为新的尾结点）将第一个结点链接到链表的尾部，作为新的尾结点 （3）返回的线性表为（a 2,a 3,…,a n ,a 1）32. ①(i＋1)%2(或1－i) ②Q－>rear[i] ③(Q－>rear[i]＋)%Maxsize 33.(1)Leafhead F H G D ∧（2）中序遍历二叉树，按遍历序列中叶子结点数据域的值构建一个以Leafhead为头指针的逆序单链表（或按二叉树中叶子结点数据自右至左链接成一个链表）。

一、单选题：C D B A A A C B C C二、填空题：n n/2 7 n2+2n3+…..+(m-1)n m+1 只有根节点的二叉树逆序1000000 2000 最大24三、应用题1、参考答案A B C D E F G H10 001 11 0001 0110 0111 010 00002、0 1 2 3 4 5 6 7 8 9 1012 100 25 16 17 18 8 40 7(1) (2) (1) (1) (1) (1) (1) （3）(4)搜索成功的平均搜索长度为ASL succ = 19(1 + 2+ 1 + 1 + 1 + 1 +1+ 3+ 4) = 533、4、最小生成树或最小生成树不唯一，有两棵，如上所示。

5、四、算法设计题1、void Bucketsort ( ElementType A[ ], int N )12 45635 6 11 1618 1 24563{int Counter[ 3 ];int i, j, k;for ( i = 0; i < 3; i++ )Counter[ i ] = 0;for ( i = 0, i < N; i++ ) {if ( A[ i ] == false )Counter[ 0 ] ++;elseif ( A[ i ] == maybe )Counter[ 1 ] ++;elseCounter[ 2 ] ++;}k = 0;for ( i = 0; i < Counter[ 0 ]; i++ )A[ i ] = false;k += Counter[ 0 ];for ( i = 0; i < Counter[ 1 ]; i++ )A[ k+i ] = maybe;k += Counter[ 1 ];for ( i = 0; i < Counter[ 2 ]; i++ )A[ k+i ] = true;}2、int BinaryTree<Type> :: leaf ( BinTreeNode<Type> * ptr ) {if ( ptr == NULL ) return 0;else if ( ptr->leftChild == NULL && ptr->rightChild == NULL ) return 1;else return leaf ( ptr->leftChild ) + leaf ( ptr->rightChild );}3、int max=0;int Find_All_Path(Graph *G,int S,int T, int K)/{G->setMark(S,VIEITED);if(S==T) //找到了一条简单路径{ if (max<K) max=K; return(max); }elsefor(int p=G->first(S);p<G->n();p=G->next(S,p){if(G->getMark(p)==UNVISITED) Find_All_Path(G,p,T,k+1); //继续寻找}G->setMark(S,UNVIEITED); }。

数据结构试卷（三）一、选择题(每题2分，共20分)1. 设某数据结构的二元组形式表示为A=(D，R)，D={01，02，03，04，05，06，07，08，09}，R={r}，r={<01，02>，<01，03>，<01，04>，<02，05>，<02，06>，<03，07>，<03，08>，<03，09>}，则数据结构A是( B )。

A. 线性结构B. 树形结构C. 物理结构D. 图形结构2. 下面程序的时间复杂度为( B )。

1 i=12 s=03 w hile i<=n:4 i +=15 t =16 for j in range(1,i):7 t = t * j8 s = s + tA. O(n)B. O(n2)C. O(n3)D. O(n4)3. 设指针变量p指向单链表中的结点A，若删除单链表中的结点A，则需要修改指针的操作序列为( A )。

A. q=p.next； p.data=q.data； p.next=q.next；B. q=p.next； q.data=p.data； p.next=q.next；C. q=p.next； p.next=q.next；D. q=p.next； p.data=q.data；4. 设有n个待排序的记录关键字，在堆排序中需要( A )个辅助记录单元。

A. 1B. nC. nlog2nD. n25. 设一组记录关键字为(20，15，14，18，21，36，40，10)，则以20为基准记录的一趟快速排序结束后的结果为( A )。

A. 10，15，14，18，20，36，40，21B. 10，15，14，18，20，40，36，21C. 10，15，14，20，18，40，36，21D. 15，10，14，18，20，36，40，216. 设二叉排序树中有n个结点，则二叉排序树的平均查找长度为( B )。

试卷B一、选择题（本题共20分,每题2分）1．在数据结构中，从逻辑上可以把数据结构分成（ ） 。

A ．动态结构和静态结构 B. 线性结构和非线性结构 C. 紧凑结构和非紧凑结构 D. 内部结构和外部结构 2. 下列程序段的时间复杂度是（ ）count=0;for(k=1;k<=n;k*=2) for(j=1;j<=n;j++) count++;A.O(nlog2n)B.O(n)C.O(log2n)D.O(n2) 3. 以下描述错误的是：（ ）A. 线性表是n 个数据元素的有限非空集合。

B. 栈和队列都是操作受限的线性表。

C. 串（或字符串）是由零个或多个字符组成的有限序列。

D. 非空栈中的栈顶指针top 始终指向栈顶元素的下一个位置。

4. 若采用少用一个队列空间的方法来区分队满队空两种状态，则判定一个顺序循环队列 Q （最大队列长度MAXSIZE ）为满队列的条件是( )。

A. Q.front=Q.rearB. Q.front!=Q.rearC. Q.front=(Q.rear+1) % MAXSIZED. Q.front!=(Q.rear+1) % MAXSIZE 5. 按照二叉树的定义，具有 3 个结点的二叉树有（ ）种。

A. 3 B. 4 C. 5 D. 66. 设矩阵A （如下图所示）是一个对称矩阵，为了节省存储，将其下三角（包括对角线）部分按行序存放在一维数组 B[n(n+1)/2]中，对下三角部分中任一元素 ai,j(i ≥j)，在一维数组 B 的下标位置k 的值是（ ）。

A. i(i-1)/2+j-1 B. i(i-1)/2+j C. i(i+1)/2+j-1 D. i(i+1)/2+j0,01,01,11,01,11,1...............n n n n a a a A a a a ----⎡⎤⎢⎥⎢⎥=⎢⎥⎢⎥⎣⎦7. 有一个有序表为｛5, 18，23, 33, 42, 54,56,78｝，当折半查找56时，经过（ ）次比较后查找成功。

《数据结构》期末复习题及参考答案- 第3章栈和队列一、选择题1、对于栈，操作数据的原则是（）。

A. 先进先出B. 后进先出C. 后进后出D. 不分顺序2、要求数据遵循FIFO（先进先出）原则的数据结构是（）。

A. 线性表B. 链表C. 队列D. 栈3、若进栈的序列为1,2,3,4，则以下哪一个不可能是一个出栈序列。

A. 5 4 3 6 1 2B. 4 5 3 1 2 6C. 3 4 6 5 2 1D. 2 3 4 1 5 65、设栈的输入序列是1，2，3，4,则（）不可能是其出栈序列。

(A) f->next=c；f=s (B) r->next=s；r=s(C) s->next=r；r=s (D) s->next=f；f=s7、一个栈的输入序列为1 2 3 4 5，则下列序列中不可能是栈的输出序列的是（）。

A. 2 3 4 1 5B. 5 4 1 3 2C. 2 3 1 4 5D. 1 5 4 3 28、数字1、2依次入栈，则出栈的顺序可能有（）种情况；数字1、2依次进入队列，则出队列的顺序可能有（）种情况。

A. 1 , 2B. 2 , 1C. 2 , 2D. 1 , 19、设一个栈的输入序列是1，2，3，4，5，则下列序列中，是栈的合法输出序列的是（）。

A. a，c，b，dB. b, c，d，aC. c, d，b, aD. d, c，a，b11、顺序存储的栈和队列中已经各有N个结点，要删除一个结点分别需要移动数据（）次和（）次。

A. N/2 , NB. N , N/2C. 0 , ND. N , 012、设有三个元素X，Y，Z顺序进栈（进的过程中允许出栈），下列得不到的出栈排列是( )。

A. 递归部分B. 终止条件和递归部分C. 迭代部分D.终止条件和迭代部分14、如下四个选项中，那个选项是能够正确判断循环队列是否排满元素的操作（其中MAXQSIZE表示队列的容量）（）：A．if (Q.rear == Q.front) …B．if (Q.rear == (Q.front + MAXQSIZE))C．if (Q.rear == (Q.front + 1) % MAXQSIZE)的元素个数为（）。

广州大学学年第学期考试卷课程数据结构与算法考试形式（闭卷，考试）信息学院系专业级班学号：姓名：一、填空题：（每格2分，共20分）1．在双向循环链表中，设指针p指向待删除的结点，则删除结点p需执行的语句为_________________ 。

2．由a, b, c三个结点构成的二叉树，共有种不同的结构。

3．设根结点处在第一层，那么具有n个结点的完全二叉树，其高度为。

4．克鲁斯卡尔的时间复杂度为；它对图较为适合。

5．给定表（55，63，44，38，75，80，31，56），用筛选法建立初始堆，则初始堆表为。

6．已知二叉树中叶子数为50，仅有一个孩子的结点数为30，则总结点数为。

7．已知8个数据元素由（35，75，40，15，20，55，95，65）按照依次插入结点的方法生成一棵二叉排序树后，最后两层上的结点总数为8．假设有n个关键字，它们具有相同的Hash函数值，用线性探测方法解决冲突，把这n个关键字散列到大小为n的地址空间中，共计需要做次插入和探测操作。

9．如果含n个顶点的图形成一个环，则它有颗生成树。

10．对有17个元素的有序表A[1..17]作二分查找，在查找其等于A[8]的元素时，被比较的元素的下标依次是。

二、单项选择题（每题1分，共10分）1．（）线性表采用链式存储时，其地址是（）A．必须是连续的B．一定是不连续的C．部分地址必须是连续的D．连续与否均可以2．（）串的逻辑结构与（）的逻辑结构不同A．线性表B．栈C．队列D．树3．（）设一数列的顺序为1，2，3，4，5，6，通过栈结构不可能排成的顺序数列为A．3，2，5，6，4，1B．1，5，4，6，2，3C．2，4，3，5，1，6D．4，5，3，6，2，14．（）设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主存储，a11为第一个元素，其存储地址为1，每元素占一个存储空间，则a85的地址为A．13B．33C．18D．405．（）二叉树在线索化后，仍不能有效求解的问题是A．前（先）序线索二叉树中求前（先）序后继；B．中序线索二叉树中求中序后继；C．中序线索二叉树中求中序前趋；D．后序线索二叉树中求后序后继。

数据结构考试试题及答案一、选择题（每题2分，共20分）1. 在数据结构中，线性表的顺序存储结构通常使用什么类型的数据结构来实现？A. 栈B. 队列C. 数组D. 链表答案：C2. 下列选项中，哪一个不是二叉树的性质？A. 任意节点的左子树和右子树的深度可能不同B. 任意节点的左子树和右子树的深度相同C. 任意节点的左子树和右子树的节点数可能不同D. 任意节点的左子树和右子树的节点数相同答案：B3. 哈希表的冲突解决方法不包括以下哪种？A. 开放定址法B. 链地址法C. 线性探测法D. 排序法答案：D4. 以下哪种排序算法的时间复杂度最低？A. 冒泡排序B. 快速排序C. 插入排序D. 归并排序答案：B5. 在图的遍历算法中，深度优先搜索（DFS）使用的栈是：A. 系统栈B. 显式栈C. 隐式栈D. 以上都不是答案：B6. 以下哪种数据结构可以有效地实现稀疏矩阵的存储？A. 顺序存储B. 链表C. 散列D. 邻接矩阵答案：C7. 在二叉搜索树中，插入一个新节点后，树的平衡因子可能为：A. -2B. 0C. 2D. 3答案：A8. 堆数据结构中，父节点的值总是大于其子节点的值，这种堆被称为：A. 最小堆B. 最大堆C. 完全二叉树D. 满二叉树答案：B9. 以下哪个算法不是动态查找表的算法？A. 直接查找B. 二分查找C. 斐波那契查找D. 哈希查找答案：A10. 在图的遍历算法中，广度优先搜索（BFS）使用的栈是：A. 系统栈B. 显式栈C. 隐式栈D. 以上都不是答案：C二、填空题（每题2分，共20分）1. 在数据结构中，栈是一种______结构，遵循后进先出（LIFO）的原则。

答案：线性2. 一个具有n个顶点的无向图的边数最多为______。

答案：n*(n-1)/23. 快速排序算法的时间复杂度在最坏情况下为______。

答案：O(n^2)4. 在哈希表中，如果一个关键字的哈希地址已经被占用，则需要进行______。

大工19秋《数据结构》在线作业3
试卷总分:100 得分:100
一、单选题 (共 10 道试题,共 50 分)
1.对线性表进行二分查找时,要求线性表必须( )。

A.以顺序方式存储,且数据元素有序
B.以顺序方式存储
C.以链接方式存储,且数据元素有序
D.以链接方式存储
标准参考解析:A
2.散列表的地址区间为0-17,散列函数为H(K)=K mod 17。

采用线性探测法处理冲突,并将关键字序列26,25,72,38,8,18,59依次存储到散列表中。

元素59存放在散列表中的地址是( )。

A.9
B.8
C.11
D.10
标准参考解析:C
3.下面给出的四种排序法中( )排序法是不稳定性排序法。

A.直接插入排序
B.堆排序
C.冒泡排序
D.二路归并排序
标准参考解析:B
4.下列排序方法中,哪一个是稳定的排序方法?( )
A.直接选择排序
B.快速排序
C.希尔排序
D.二分法插入排序
标准参考解析:D
5.下面给出的四种排序方法中,排序过程中的比较次数与排序方法无关的是( )。

A.选择排序法
B.插入排序法
C.快速排序法
D.堆排序法
标准参考解析:A
6.在下面的排序方法中,辅助空间为O(n)的是( ) 。

A.选择排序
B.归并排序
C.希尔排序。

数据结构练习试卷3(题后含答案及解析)题型有：1. 选择题选择题（每小题1分，共75分）下列各题A、B、C、D四个选项中，只有一个选项是正确的，请将此选项涂写在答题卡相应位置上，答在试卷上不得分。

1．二叉树(1)。

在完全的二叉树中，若一个结点没有(2)，则它必定是叶结点。

每棵树都能唯一地转换成与它对应的二叉树。

由树转换成的二叉树里，一个结点N的左子结点是N在原树里对应结点的(3)，而N的右子结点是它在原树里对应结点的(4)。

A．是特殊的树B．不是树的特殊形式C．是两棵树的总称D．是只有两个根结点的树形结构正确答案：B 涉及知识点：数据结构2．A．左子结点B．右子结点C．左子结点或者没有右子结点D．兄弟正确答案：A 涉及知识点：数据结构3．A．最左子结点B．最右子结点C．最邻近的右兄弟D．最邻近的左兄弟正确答案：A 涉及知识点：数据结构4．A．最左子结点B．最右子结点C．最邻近的右兄弟D．最邻近的左兄弟正确答案：C解析：树是结点的有限集合，它有且仅有1个根结点。

二叉树有0个或1个根结点，二者是两个不同的概念。

所以，第1空的正确答案为选项B。

在完全二叉树中，如果一个结点没有左子结点，那么必然没有右子结点，所以就一定是叶结点。

第2空的正确答案为选项A。

树中每个结点最多只有一个最左边的孩子(长子)和一个右邻的兄弟。

按照这种关系很自然地就能将树转换成相应的二叉树：①在所有兄弟结点之间加一连线；②对每个结点，除了保留与其长子的连线外，去掉该结点与其他孩子的连线。

因为树根没有兄弟，所以，树转换为二叉树之后，二叉树的根结点的右子树必然为空。

在由树转换成的二叉树中，一个结点N的左一个结点N的左子结点是N在原树里对应结点的最左子结点，而N的右子结点是它在原树里对应结点的最邻近的右兄弟。

所以，第3空的正确答案为选项A，第4空的正确答案为选项C。

知识模块：数据结构5．在一棵非空二叉树中，叶子节点的总数比度为2的节点总数多(43)个。

数据结构试卷（一）一、单选题（每题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．6965.树最适合用来表示( ）.A。

有序数据元素 B.无序数据元素C.元素之间具有分支层次关系的数据D。

元素之间无联系的数据6.二叉树的第k层的结点数最多为( ）.A．2k-1 B。

2K+1 C.2K-1 D。

2k—17.若有18个元素的有序表存放在一维数组A［19]中，第一个元素放A[1]中，现进行二分查找，则查找A［3]的比较序列的下标依次为( ）A. 1，2，3B. 9，5，2,3C. 9，5，3 D。

9，4,2,38.对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．410.设有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））,则树中所含的结点数为__________个，树的深度为___________，树的度为_________。

模拟试题三模拟试题三一、选择题（30分）1.下面程序的时间复杂度为( )。

for(i=O;i<m;i++)for(j=0;j<t;j++)c[i][j]=O;for(i=O;i<m;i++)for(j=O;j<t;j++)for(k=O;k< SPAN>c[i][j]=c[i][j]+a[i][k]b[k][j];A) O (mnt) B)0(m+n+t) C) O(m+nt) D)O(mt+n)2.从一个长度为n的顺序表中删除第i个元素(1≤i≤n)，需向前移动( )个元素。

A) n-i B) n-i+l C) n-i-l D)i3.串的逻辑结构与( )的逻辑结构不同。

A)线性表 B)栈 C)队列 D)树4.二叉树第i(i≥1)层最多有( )个结点。

A) 2i B) 2i C) 2i-l D) 2i-15.设单链表中指针p指向结点A，若要删除A之后的结点（若存在），则修改指针的操作为( )。

A) p->next=p->next->next B) p=p->nextC) p=p->next->next D)p->next=p6.设一数列的输入顺序为l，2，3，4，5，6，通过栈操作不可能排成的输出序列为( )。

A)3,2,5,6,4,l B)l,5,4,6,2,3C)2,4,3,5,l,6 D)4,5,3,6,2,l7。

设字符串Sl=‘ABCDEFG’，S2=‘PQRST’，则运算S=Concat(Sub(S1，2，Length(S2))Sub(S1，Length(S2)，2))后结果为( )。

A)‘BCQR' B)‘BCDEF'C)‘BCDEFG' D)‘BCDEFEF'8.设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主存储，all为第1个元素，其存储地址为1，每个元素占用1个地址空间，则a85的地址为( )A) 13 B) 33 C) 18 D) 409.如果结点A有3个兄弟，且B为A的双亲，则B的度为( )。

第3章‎线性表的链‎式存储‎3.1‎选择题（‎1）两个有‎序线性表分‎别具有 n‎个元素与‎m个元素且‎n≤m，‎现将其归并‎成一个有序‎表，其最‎少的比较次‎数是（ A‎）。

‎A．n B‎．m C．‎n . 1‎D．m ‎+ n（‎2）非空的‎循环单链表‎head‎的尾结点（‎由 p所指‎向）满足（‎C）。

‎A．p-‎>next‎==NUL‎L B．p‎==NUL‎L C．p‎->nex‎t==he‎a d D．‎p==he‎a d（‎3）在带头‎结点的单链‎表中查找‎x应选择的‎程序体是（‎C ）。

‎A．n‎o de *‎p=hea‎d->ne‎x t; w‎h ile ‎(p &&‎p->i‎n fo!=‎x) p=‎p->ne‎x t;‎i f (p‎->inf‎o==x)‎retu‎r n p ‎e lse ‎r etur‎n NUL‎L;B‎．node‎*p=h‎e ad; ‎w hile‎(p&&‎p->i‎n fo!=‎x) p=‎p->ne‎x t; r‎e turn‎p;‎C．nod‎e *p=‎h ead-‎>next‎; whi‎l e (p‎&&p->‎i nfo!‎=x) p‎=p->n‎e xt; ‎r etur‎n p; ‎D．no‎d e *p‎=head‎; whi‎l e (p‎->inf‎o!=x)‎p=p-‎>next‎; re‎t urn ‎p;（4‎）线性表若‎采用链式存‎储结构时，‎要求内存中‎可用存储单‎元的地址（‎D ）。

‎A．必‎须是连续的‎B．部分‎地址必须是‎连续的‎C．一定是‎不连续的‎D．连续不‎连续都可以‎（5）在‎一个具有‎n个结点的‎有序单链表‎中插入一个‎新结点并保‎持单链表仍‎然有序的时‎间复杂度‎是（ B ‎）。

第三章栈和队列答案部分答案解释如下。

1、尾递归的消除就不需用栈2、这个数是前序序列为1,2,3,…,n，所能得到的不相似的二叉树的数目。

三、填空题1、操作受限（或限定仅在表尾进行插入和删除操作）后进先出2、栈3、3 1 24、23 100CH5、0 n+1 top[1]+1=top[2]6、两栈顶指针值相减的绝对值为1（或两栈顶指针相邻）。

7、(1)满 (2)空 (3)n (4)栈底 (5)两栈顶指针相邻（即值之差的绝对值为1）8、链式存储结构 9、S×SS×S×× 10、data[++top]=x；11、23.12.3*2-4/34.5*7/++108.9/+（注：表达式中的点(.)表示将数隔开，如23.12.3是三个数）12、假溢出时大量移动数据元素。

13、(M+1) MOD N (M+1)% N； 14、队列 15、先进先出 16、先进先出 17、s=(LinkedList)malloc(sizeof(LNode))； s->data=x;s->next=r->next；r->next=s；r=s；18、牺牲一个存储单元设标记19、（TAIL+1）MOD M=FRONT (数组下标0到M-1，若一定使用1到M，则取模为0者，值改取M20、sq.front=(sq.front+1)%(M+1)；return(sq.data(sq.front))；(sq.rear+1)%(M+1)==sq.front；21、栈 22、（rear-front+m）% m； 23、（R-P+N）% N；24、（1）a[i]或a[1] （2）a[i] （3）pop（s）或s[1]；25、（1）PUSH（OPTR，w）（2）POP（OPTR）（3）PUSH（OPND，operate（a，theta，b））26、（1）T>0（2）i<n（3）T>0（4）top<n（5）top+1（6）true（7）i-1（8）top-1（9）T+w[i]（10）false四、应用题1、栈是只准在一端进行插入和删除操作的线性表，允许插入和删除的一端叫栈顶，另一端叫栈底。