02142《数据结构导论》复习题.

1、1数据结构导论模拟试题一、考试题型及分值分布：1、单项选择题 (本大题共 15 小题，每小题 2 分，共 30 分)2、填空题 (本大题共 13 小题，每小题 2 分，共 26 分)3、应用题 (本大题共 5 小题，每小题 6 分，共 30 分)4、算法设计题 (本大题共 2 小题，每小题 7 分，共 14 分) 二、单项选择题和填空题样题参考(一)单项选择题1.在二维数组中，每个数组元素同时处于( )个向量中。A. 0 B. 1 C. 2 D. n2.已知单链表A长度为 m 单链表 B 长度为 n 它们分别由表头指针所指向，若将B整体连接到 A 的末尾，其时间复杂度应为()。A. O(1)

2、B. O(m) C. O(n) D. O(m+n)3.假定一个链式队列的队头和队尾指针分别为 front 和 rear ，则判断队空的条件为 ( ) 。A. front = rear B. front != NULLC. rear != NULL D. front = NULL4.若让元素 1,2,3 依次进栈，则出栈次序不可能出现 ( ) 种情况。A. 3,2,1 B. 2,1,3 C. 3,1,2 D. 1,3,25.图的广度优先搜索类似于树的( )遍历。A. 先根 B. 中根 C. 后根 D. 层次6.下面程序段的时间复杂度为 ( ) 。for(int i=0; im; i+)for(i

3、nt j=0; jlink=s; B.s-link=top-link; top-link=s;C. s-link=top; top=s; D. s-link=top; top=top-link;10. 一棵具有 35 个结点的完全二叉树的高度为 ( ) 。假定空树的高度为 -1 。A. 5 B. 6 C. 7 D. 811. 一个有 n 个顶点和 n 条边的无向图一定是()的。A 连通 B.不连通C .无回路 D .有回路C Head(Tail(Head(Tail(A) DHead(Head(Tail(Tail(A)12.13.在一个长度为 n 的顺序表的任一位置插入一个新元素的时间复杂度为(

4、A. O(n) B. O(n/2) C. O(1) D. O(n2)已知广义表为 A(a,b,c),(d,e,f)，从 A 中取出原子 e 的运算是()。)。A. Tail(Head(A)BHead(Tail(A)214.在一棵树的静态双亲表示中，每个存储结点包含 ( ) 个域。A 1 B 2 C 3 D 415.有向图中的一个顶点的度数等于该顶点的 ( ) 。A 入度B.出度C.入度与出度之和D .(入度+出度)/215. 与邻接矩阵相比，邻接表更适合于存储 ( ) 。A 无向图 B.连通图C .稀疏图 D .稠密图17.较快的数据搜索方法是( )搜索方法。A. 顺序 B. 折半 C. 单链

5、 D. 散列18.在闭散列表中，散列到同一个地址而引起的“堆积”问题是由于( )引起的。A. 同义词之间发生冲突B.非同义词之间发生冲突C. 同义词之间或非同义词之间发生冲突 D. 散列表“溢出”19.根据 n 个元素建立一个有序单链表的时间复杂度为()。2A. O(1) B. O(n) C. O(n2)D. O(nlog2n)20.假定一个顺序存储的循环队列的队头和队尾指针分别为front 和 rear ，则判断队空的条件为 ( ) 。A. front+1=rear B. rear+1=frontC. front=0 D. front=rear21. 假定一棵二叉树的第 i 层上有 3i 个

6、结点，则第 i+1 层上最多有 ( ) 个结点。A. 3i B. 6i C. 9i D. 2i22.对于具有 e 条边的无向图，它的邻接表中共有()个边结点。A e-1 B e+1 C 2e D 3e23.图的深度优先搜索遍历类似于树的( )次序遍历。A. 先根B.中根C.后根D.层次24 栈 S 最多能容纳 4 个元素。现有6 个元素按 A、B、C、D、E、F 的顺序进栈 , 问下列哪一个序列是可能的出栈序列 ?()A. E 、 D、 C、 B、 A、FB. B、 C、E、F、A、DC. C 、 B、 E、 D、 A、FD. A、 D、F、E、B、C25 将一棵有 100 个结点的完全二叉树

7、从根这一层开始，每 一层从左到右依次对结点进行编号，根结点编号为 1，则编号为 49 的结点的左孩子的编号为： ( )A. 98 B. 99 C. 50 D. 4826.对下列关键字序列用快速排序法进行排序时，速度最快的情形是：( )A. 21 、 25、5、 17、9、23、30B. 25 、 23、30、17、21、5、9B. 21 、 9、17、 30、 25、 23、 5D. 5 、9、17、21、23、 25、3027对于只在表的首、尾进行插入操作的线性表，宜采用的存储结构为( )A. 顺序表B.用头指针表示的单循环链表C.用尾指针表示的单循环链表 D. 单链表28假设以第一个元素为

8、分界元素，对字符序列( Q, H, C, Y, P, A, M, S, R, D, F,X)进行快速排序，则第一次划分的结果是：()A. (A, C, D, F, H, M, P, Q, R, S, X, Y)B. (A, F, H, C, D, P, M, Q, R, S, Y, X)C. (F, H, C, D, P, A, M, Q, R, S, Y, X)D. (P, A, M, F, H, C, D, Q, S, Y, R, X)29下面是三个关于有向图运算的叙述：3（1）求有向图结点的拓扑序列，其结果必定是唯一的（2）求两个指向结点间的最短路径，其结果必定是唯一的（3）求 AOE

9、网的关键路径，其结果必定是唯一的其中哪个（些）是正确的？A.只有（1） B. （ 1 ）和（2） C. 都正确 D.都不正确30.若进栈序列为 a, b, c,则通过入出栈操作可能得到的a, b, c 的不同排列个数为（）A. 4 B. 5 C. 6 D. 731.以下关于广义表的叙述中，正确的是：（）A.广义表是由 0 个或多个单元素或子表构成的有限序列B.广义表至少有一个元素是子表C.广义表不能递归定义D）广义表不能为空表32.排序时扫描待排序记录序列， 顺次比较相邻的两个元素的大小， 逆序时就交换位置。C.快速排序 D.冒泡排序要删除所有从第 i 个结点发出的边，应该：（）B.将邻接矩阵

10、的第 i 行元素全部置为 0D.将邻接矩阵的第 i 列元素全部置为 0头指针为head,则其为空的条件是：（）C. head-n ext=headD. head-n ext- priro=NULL35.在顺序表（3, 6, 8, 10, 12, 15, 16, 18, 21,25, 30 ）中，用折半法查找关键码值 11,所需的关键码比较次数为：（）A. 2 B. 3 C. 4 D. 536.以下哪一个不是队列的基本运算？（）A.从队尾插入一个新元素B.从队列中删除第 i 个元素C.判断一个队列是否为空D.读取队头元素的值37.对包含 n 个元素的哈希表进行查找，平均查找长度为：（）A. O（

11、log2n） B. O（n） C. O（nlog2n） D38.将一棵有 100 个结点的完全二叉树从根这一层开始， 行编号，根结点编号为1,则编号最大的非叶结点的编号为：A. 48 B. 49 C. 50 D. 5139.某二叉树结点的中序序列为 E,则其左子树中结点数目为：（）A. 3 B. 2C. 4D. 540._ 下面是顺序存储结构的优点。A.存储密度大 B.插入运算方便C.查找方便D.适合各种逻辑结构的存储表示41 .下面关于串的叙述中， _是不正确的。A.串是字符的有限序列B.空串是由空格构成的串C.模式匹配是串的一种重要运算D.串既可以采用顺序存储，也可以采用链式存储这是哪种排

12、序方法的基本思想？（）A.A. head-priro=NULLB. head- next=NULL不直接依赖于 n每一层从左到右依次对结点进（）AB、C、DE、F、G 后序序列为B、D、C A、F、G442._的邻接矩阵是对称矩阵。A.有向图 B.无向图 C. AOV 网 D. AOE 网43.用链式方式存储的队列，在进行删除运算时， _。44.二叉树的先序遍历和中序遍历如下，则该二叉树右子树的树根是_先序序列：EFHIGJK中序序列：HFIEJKGA. E B. F C. G D. H45._下面方法可以判断出一个有向图中是否有环。A.深度优先遍历B. 拓朴排序 C.求最短路径D.求关键路径

13、46.从未排序序列中依次取出一个元素与已排序序列中的元素依次进行比较，然后将其放在已排序序列的合适位置，该排序方法称为 _ 排序法。A.插入 B. 选择 C. 冒泡 D. 都不是47.个栈的入栈序列是a,b,c,d,e，则栈的不可能的输出序列是 _ 。A.edcba B.decba C.dceab D. abcde48.n 个节点的完全二叉树，编号为_ i 的节点是叶子结点的条件是。A. in B. 2*in D. 2*in49.向一个有128 个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要移动个元素。A. 64.5 B. 64 C. 63 D. 6550.在一个单链表HL 中，若要

14、在指针 q 所指结点的后面插入一个由指针p 所指向的结点，则执行_ 。A. q_n ext=p-n ext; p_n ext=q;B. p_n ext=q _n ext; q=p;C. p_n ext=p-n ext; q_n ext=q;D. p_n ext=q _n ext; q_n xet=p;51 .对一个满二叉树，m 个树叶，n 个结点，深度为 h,则有_ 。A. n=h+m B. h+m=2 n C. m=h-1 D. n=2h-152._在所有排序方法中，关键字比较的次数与记录的初始排列次序无关的是 _A.选择排序 B.冒泡排序 C.插入排序 D.希尔排序53._ 用链式方式存储

15、的队列，在进行插入运算时， _ 。A.仅修改头指针B.仅修改尾指针C.头、尾指针都要修改D. 头、尾指针可能都要修改54.在一个长度为 n 的顺序存储的线性表中，向第 i 个元素(K i n+1)插入一个新A.仅修改头指针B.仅修改尾指针C.头、尾指针都要修改D. 头、尾指针可能都要修改5元素时，需要从后向前依次后移 _ 个元素。A. n-i B. n-i-1 C. n-i+1 D. i55.一个栈的入栈序列是_ 12345，则栈的不可能的输出序列是。A.23415 B.54132 C.23145 D.1543256.5 个顶点的有向图最多有 _条弧。A. 5 B. 20 C. 4 D. 25

16、57 .假定一个链队的队首和队尾指针分别为front 和 rear，则判断队空的条件为_ 。A. fron t=rear B. fron t!=NULLC. rear!=NULL D. fron t=NULL58.若某线性表中最常用的操作是提取第i 个元素及找第 i 个元素的前驱元素，则采用()存储方式最省时间。A.单链表B. 双链表 C.单向循环链表 D.顺序表59.将含有 100个结点的完全二叉树从根开始自上向下，每层从左到右依次编号，且设根结点的编号为 1,则编号 69 的结点的双亲的编号为()。A. 34 B. 35 C. 33 D.无法确定60.单循环链表的主要优点是()。6A. 不

17、再需要头指针了B. 已知某结点的位置后，很容易找到其前驱C. 在进行插入、删除运算时，能更好地保证链表不断开D. 从表中任一结点出发都能扫描到整个链表61. 一个栈的入栈顺序是 1、2、3、4、5，则此栈不可能的输出顺序为（A. 5、4、3、2、 1B. 4、5、3、2、1C. 4、3、5、1、262.串是一种特殊的线性表，A.可以顺序存储C 可以链式存储D. 1其特殊性表现在（B.D.63. n 个顶点的无向图中最多有（）A. n（n-1）/2 B. n（n-1）C. n （n+1）64. 6 个顶点的无向图中，至少有（A. 5 B. 6 C. 7 D. 865. 若某线性表中最常用的操作是

18、删除第A.单链表 B. 双链表 C.66. 在一棵完全二叉树的顺序存储方式中，号为（67.68.素。）A. 2i B. 2i-1按照二叉树的定义，具有A. 3在长为B. 4n 的顺序表中，删除第B. n-i+169.A. n-i一个队的入队顺序是A. 5、4、3、2、 1、2、3、4、5）数据元素是一个字符数据元素是多个字符 条边。D. n（n+1）/2）条边才能保证是一个连通图。1 个元素，则不宜采用（单向循环链表 D.顺序表若编号 i 的结点有右孩子，则其右孩子的编C. 2i+1 D. i/23 个结点的二叉树有（D. 6i 个元素（1 i n+1）需要向前移动（）种不同形态。C. 5C.

19、 n-i-11、2、3、B. 4D. i4、5, 则此队的出队顺序为（、5、3、2、1）存储方式。）个元C. 4、3、5、1、2栈是一种特殊的线性表，A.可以顺序存储C.可以链式存储71.一棵二叉树中，第A. 2k B.2k-170.D. 1其特殊性表现在B.D.k 层上最多有（C.2、2、3、4、5（ ）只能从端点进行插入和删除可以在任何位置进行插入和删除 ）个结点。D.2k-172.一棵有 18 个结点的二叉树，其高度最小为（A. 473. 有向图中，A. 0.5（二）填空题1.数据元素之间存在的相互关系称为2. 数据结构从逻辑上分为_结构和3. 线性表的顺序存储结构称为 _。4. 所有插

20、入在表的一端进行，而所有删除在表的另一端进行的线性表称为5. 深度为 h 的二叉树，最少有_ 个结点。6. 折半查找要求待查表为 _ 表。7.n 个记录按其关键字大小递增或递减的次序排列起来的过程称为B. 5 C. 6D. 18所有顶点入度和是所有顶点出度和的（B. 1 C. 2D. 4O结构。层。）倍。788.存储数据时,不仅要存储数据元素的,还要存储元素之间的相互 _。9 将一棵有 100 个结点的完全二叉树按层编号，则编号为49 的结点 X,其双亲 PARENTX)的编号为_ _。10、 一个字符串相等的充要条件是 _和_。11、 在有向图的邻接表和逆邻接表表示中，每个顶点的边链表中分别

21、链接着该顶点的所有和_结点。11、 在一个长度为 n 的顺序表中向第 i 个元素(0i n)的排好序的表归并成一个排好序的表， 至少要进行 _次键值比较。通常从四个方面评价算法的质量： _、_、_ 和_。31、一个算法的时间复杂度为(n3+nlog2n+14n)/n2，其数量级表示为 _。32、若用链表存储一棵二叉树时，每个结点除数据域外，还有指向左孩子和右孩子的两个指针。在这种存储结构中，n 个结点的二叉树共有 _个指针域，其中有 _ 个指针域是存放了地址，有_个指针是空指针。33、对于一个具有 n 个顶点和 e 条边的有向图和无向图，在其对应的邻接表中， 所含边结点分别有_ 个和_个。34

22、、在一个具有 n 个顶点的无向完全图中， 包含有_条边，在一个具有 n 个顶点的有向完全图中，包含有 _ 条边。35、36.在快速排序、堆排序、归并排序中， _排序是稳定的。36、37.中序遍历二叉排序树所得到的序列是 _序列。38. 快速排序的最坏时间复杂度为 _，平均时间复杂度为_。39. 设一组初始记录关键字序列为(55，63, 44，38，75，80，31，56)，则利用筛选法建立的初始堆为_。940 数据的物理结构主要包括 _和_ 两种情况。1041._设一棵完全二叉树中有 500 个结点，则该二叉树的深度为 _；若用二叉链表作为该完全二叉树的存储结构，则共有 _ 个空指针域。42、

23、设输入序列为1、2、 3，则经过栈的作用后可以得到 _种不同的输出序列。43、设有向图 G 用邻接矩阵 Ann作为存储结构，则该邻接矩阵中第 i 行上所有元素之和 等于顶点 i的_，第 i 列上所有元素之和等于顶点 i 的 。设哈夫曼树中共有 n 个结点,则该哈夫曼树中有 _ 个度数为 1 的结点。设有向图 G 中有 n 个顶点 e 条有向边，所有的顶点入度数之和为d,则 e 和 d 的关系为_ 遍历二叉排序树中的结点可以得到一个递增的关键字序列 (填先序、 中序或 后序)。设查找表中有 100 个元素，如果用二分法查找方法查找数据元素X， 则最多需要比较次就可以断定数据元素 X 是否在查找表

24、中。 不论是顺序存储结构的栈还是链式存储结构的栈， 其入栈和出栈操作的时间复杂度均为设有 n 个结点的完全二叉树， 如果按照从自上到下、 从左到右从 1 开始顺序编号， 则第 i 个结点的双亲结点编号为 _，右孩子结点的编号为 _ 。设一组初始记录关键字为 (72 ， 73， 71， 23， 94， 16， 5)，则以记录关键字 72 为基准的一趟快速排序结果为 _ 。设有向图 G 中有向边的集合E=1，2，2，3，1，4，4，2，4，3，则该图的一种拓扑序列为 _ 。下列算法实现在顺序散列表中查找值为 x 的关键字，请在下划线处填上正确的语句。 struct recordi ntkey; i

25、nt others;int hashsqsearch(struct record hashtable ,int k)int i,j; j=i=k % p;while (hashtablej.key!=k&hashtablej.flag!=0)j=(_ )%m; if (i=j)return(-1);if (_ ) return(j); else return(-1); j+1， hashtablej.key=k下列算法实现在二叉排序树上查找关键值k，请在下划线处填上正确的语句。typedef struct nodeint key; struct node *lchild; struct

26、 node *rchild;bitree; bitree *bstsearch(bitree*t, int k)if (t=0 ) return(0);else while (t!=0)if (t-key=k)_ ;else if (t-keyk) t=t-lchild;else_ ;return(t) ， t=t-rchild设有 n 个无序的记录关键字， 则直接插入排序的时间复杂度为 _ ， 快速排序的平均时间复杂度为 _ 。44、45、46、47、48、49、50、51、52、53、54、11设指针变量 p 指向双向循环链表中的结点X，则删除结点X 需要执行的语句序列为_ (设结点中的两

27、个指针域12分别为 llink 和 rlink )。根据初始关键字序列 (19 ，22，01，38，10) 建立的二叉排序树的 高度为_ 3_ 。55、深度为 k 的完全二叉树中最少有 _ 2k-1_ 个结点。56、 设初始记录关键字序列为(Ki, K2,，Kn)，则用筛选法思想建堆必须从第_ n/2_个元素开始进行筛选。59、_ 设哈夫曼树中共有 99 个结点, 则该树中有个叶子结点； 若采用二叉链表作为存储结构,则该树中有 _ 个空指针域。60、 设有一个顺序循环队列中有M 个存储单元，则该循环队列中最多能够存储 _ 个队列元素；当前实际存储_ 个队列元素(设头指针 F 指向当前队头元素的前一个位置,尾指针指向当前队尾元素的