数据结构导论模拟试题.doc

数据结构导论 模拟试题（一）单项选择题1. 在二维数组中，每个数组元素同时处于（C ）个向量中。A. 0 B. 1 C. 2 D. n2. 已知单链表A长度为m，单链表B长度为n，它们分别由表头指针所指向，若将B整体连接到A的末尾，其时间复杂度应为（ B ）。A. O(1) B. O(m) C. O(n) D. O(m+n)3. 假定一个链式队列的队头和队尾指针分别为front和rear，则判断队空的条件为(D)。A. front = rear B. front != NULLC. rear != NULL D. front = NULL4. 若让元素1,2,3依次进栈，则出栈次序不可能出现(C)种情况。A. 3,2,1 B. 2,1,3 C. 3,1,2 D. 1,3,25. 图的广度优先搜索类似于树的（D）遍历。A. 先根 B. 中根 C. 后根 D. 层次6. 下面程序段的时间复杂度为(C)。 for(int i=0; im; i+) for(int 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个结点的完全二叉树的高度为(A)。假定空树的高度为-1。A. 5 B. 6 C. 7 D. 811. 一个有n个顶点和n条边的无向图一定是(D) 的。A连通 B不连通 C无回路 D有回路12. 在一个长度为n的顺序表的任一位置插入一个新元素的时间复杂度为（A ）。A. O(n) B. O(n/2) C. O(1) D. O(n2)13. 已知广义表为A(a,b,c),(d,e,f)，从A中取出原子e的运算是（ C ）。ATail(Head(A) BHead(Tail(A)CHead(Tail(Head(Tail(A) DHead(Head(Tail(Tail(A)14. 在一棵树的静态双亲表示中，每个存储结点包含(B)个域。A 1 B 2 C 3 D 415. 有向图中的一个顶点的度数等于该顶点的(C)。A入度 B出度 C入度与出度之和 D(入度+出度)/15. 与邻接矩阵相比，邻接表更适合于存储(C)。A无向图 B连通图 C稀疏图 D稠密图17. 较快的数据搜索方法是（ D ）搜索方法。A. 顺序 B. 折半 C. 单链 D. 散列18. 在闭散列表中，散列到同一个地址而引起的“堆积”问题是由于（B）引起的。A. 同义词之间发生冲突 B. 非同义词之间发生冲突C. 同义词之间或非同义词之间发生冲突 D. 散列表“溢出”19. 根据n个元素建立一个有序单链表的时间复杂度为（C ）。A. O(1) B. O(n) C. O(n2) D. O(nlog2n)20. 假定一个顺序存储的循环队列的队头和队尾指针分别为front和rear，则判断队空的条件为(D)。A. front+1=rear B. rear+1=frontC. front=0 D. front=rear21. 假定一棵二叉树的第i层上有3i个结点，则第i+1层上最多有(B)个结点。A. 3i B. 6i C. 9i D. 2i22. 对于具有e条边的无向图，它的邻接表中共有(C)个边结点。Ae-1 Be+1 C2e D3e23. 图的深度优先搜索遍历类似于树的（ A ）次序遍历。A. 先根 B. 中根 C. 后根 D. 层次24栈S最多能容纳4个元素。现有6个元素按A、B、C、D、E、F的顺序进栈, 问下列哪一个序列是可能的出栈序列?(C )A. E、D、C、B、A、F B. B、C、E、F、A、D C. C、B、E、D、A、F D. A、D、F、E、B、C25将一棵有100个结点的完全二叉树从根这一层开始，每一层从左到右依次对结点进行编号，根结点编号为1，则编号为49的结点的左孩子的编号为：( A )/左孩子：2*i，右孩子：2*i+1.A. 98 B. 99 C. 50 D. 4826. 对下列关键字序列用快速排序法进行排序时，速度最快的情形是：( B )A. 21、25、5、17、9、23、30 B. 25、23、30、17、21、5、9C. 21、9、17、30、25、23、5 D. 5、9、17、21、23、25、3027对于只在表的首、尾进行插入操作的线性表，宜采用的存储结构为(C)A. 顺序表 B. 用头指针表示的单循环链表C. 用尾指针表示的单循环链表 D. 单链表28假设以第一个元素为分界元素，对字符序列（Q, H, C, Y, P, A, M, S, R, D, F, X）进行快速排序，则第一次划分的结果是：(C)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下面是三个关于有向图运算的叙述：( D )（1）求有向图结点的拓扑序列，其结果必定是唯一的（2）求两个指向结点间的最短路径，其结果必定是唯一的（3）求AOE网的关键路径，其结果必定是唯一的其中哪个（些）是正确的？A. 只有（1） B. （1）和（2） C. 都正确 D. 都不正确 30若进栈序列为a, b, c，则通过入出栈操作可能得到的a, b, c的不同排列个数为: ( B )A. 4 B. 5 C. 6 D. 731. 以下关于广义表的叙述中,正确的是：( A )A. 广义表是由0个或多个单元素或子表构成的有限序列B. 广义表至少有一个元素是子表C. 广义表不能递归定义 D) 广义表不能为空表32. 排序时扫描待排序记录序列，顺次比较相邻的两个元素的大小，逆序时就交换位置。这是哪种排序方法的基本思想？( D )A. 堆排序 B. 直接插入排序 C. 快速排序 D. 冒泡排序33 已知一个有向图的邻接矩阵表示，要删除所有从第i个结点发出的边，应该：( B)A. 将邻接矩阵的第i行删除 B. 将邻接矩阵的第i行元素全部置为0C. 将邻接矩阵的第i列删除 D. 将邻接矩阵的第i列元素全部置为034 有一个含头结点的双向循环链表，头指针为head, 则其为空的条件是：( )A. head-priro=NULL B. head-next=NULL C. head-next=head D. head-next- priro=NULL此答案有问题：Head-next=Head-prior=Head;35. 在顺序表 ( 3, 6, 8, 10, 12, 15, 16, 18, 21, 25, 30 )中，用折半法查找关键码值11，所需的关键码比较次数为：( C )A. 2 B. 3 C. 4 D. 536. 以下哪一个不是队列的基本运算？( A )A. 从队尾插入一个新元素 B. 从队列中删除第i个元素C. 判断一个队列是否为空 D. 读取队头元素的值37对包含n个元素的哈希表进行查找，平均查找长度为：( D )A. O(log2n) B. O(n) C. O(nlog2n) D 不直接依赖于n38将一棵有100个结点的完全二叉树从根这一层开始，每一层从左到右依次对结点进行编号，根结点编号为1，则编号最大的非叶结点的编号为：( C )A. 48 B. 49 C. 50 D. 5139某二叉树结点的中序序列为A、B、C、D、E、F、G，后序序列为B、D、C、A、F、G、E，则其左子树中结点数目为：( C )A. 3 B. 2 C. 4 D. 540下面 A 是顺序存储结构的优点。A. 存储密度大 B. 插入运算方便 C. 查找方便 D. 适合各种逻辑结构的存储表示41下面关于串的叙述中， B 是不正确的。A. 串是字符的有限序列 B. 空串是由空格构成的串C. 模式匹配是串的一种重要运算 D. 串既可以采用顺序存储，也可以采用链式存储42 B 的邻接矩阵是对称矩阵。A. 有向图 B. 无向图 C. AOV网 D. AOE网43用链式方式存储的队列，在进行删除运算时， D 。A. 仅修改头指针 B. 仅修改尾指针 C. 头、尾指针都要修改 D. 头、尾指针可能都要修改 44二叉树的先序遍历和中序遍历如下，则该二叉树右子树的树根是 C 。先序序列：EFHIGJK 中序序列：HFIEJKG/ E是树根（头结点），由中序可知JKG都是右孩子；再有先序可得G右子树的树根.A. E B. F C. G D. H45下面 B 方法可以判断出一个有向图中是否有环。A. 深度优先遍历 B. 拓朴排序 C. 求最短路径 D.求关键路径46从未排序序列中依次取出一个元素与已排序序列中的元素依次进行比较，然后将其放在已排序序列的合适位置，该排序方法称为 A 排序法。A. 插入 B. 选择 C. 冒泡 D. 都不是47一个栈的入栈序列是a,b,c,d,e，则栈的不可能的输出序列是 C 。A. edcba B. decba C. dceab D. abcde48n个节点的完全二叉树，编号为i的节点是叶子结点的条件是 D 。A. in B. 2*in D. 2*in49向一个有128个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要移动 B 个元素。n/2A. 64.5 B. 64 C. 63 D. 6550在一个单链表HL中，若要在指针q所指结点的后面插入一个由指针p所指向的结点，则执行 D 。A. q-next=p-next; p-next=q; B. p-next=q-next; q=p;C. p-next=p-next; q-next=q; D. p-next=q-next; q-nxet=p;51对一个满二叉树，m个树叶，n个结点，深度为h，则有 D 。A. n=h+m B. h+m=2n C. m=h-1 D. n=2h-152在所有排序方法中，关键字比较的次数与记录的初始排列次序无关的是 。A. 选择排序 B. 冒泡排序 C. 插入排序 D. 希尔排序53用链式方式存储的队列，在进行插入运算时 D 。A. 仅修改头指针 B. 仅修改尾指针 C. 头、尾指针都要修改 D. 头、尾指针可能都要修改 54在一个长度为n的顺序存储的线性表中，向第i个元素（1in+1）插入一个新元素时，需要从后向前依次后移 C 个元素。A. n-i B. n-i-1 C. n-i+1 D. i55一个栈的入栈序列是12345，则栈的不可能的输出序列是 B 。A. 23415 B. 54132 C. 23145 D. 15432565个顶点的有向图最多有 B 条弧。A. 5 B. 20 C. 4 D. 2557假定一个链队的队首和队尾指针分别为front和rear，则判断队空的条件为 D 。A. front=rear B. front!=NULL C. rear!=NULL D. front=NULL58若某线性表中最常用的操作是提取第i个元素及找第i个元素的前驱元素，则采用（ D ）存储方式最省时间。A.单链表 B.双链表 C.单向循环链表 D.顺序表59将含有100个结点的完全二叉树从根开始自上向下，每层从左到右依次编号，且设根结点的编号为1，则编号69的结点的双亲的编号为（ A ）。A. 34 B. 35 C. 33 D. 无法确定60. 单循环链表的主要优点是（ C ）。A. 不再需要头指针了B. 已知某结点的位置后，很容易找到其前驱C. 在进行插入、删除运算时，能更好地保证链表不断开D. 从表中任一结点出发都能扫描到整个链表61. 一个栈的入栈顺序是1、2、3、4、5，则此栈不可能的输出顺序为（ C ）。A. 5、4、3、2、1 B. 4、5、3、2、1C. 4、3、5、1、2 D. 1、2、3、4、562. 串是一种特殊的线性表，其特殊性表现在（ D ）。A. 可以顺序存储 B.数据元素是一个字符 C可以链式存储 D.数据元素是多个字符63. n个顶点的无向图中最多有（ A ）条边。A. n(n-1)/2 B. n(n-1) C. n(n+1) D. n(n+1)/264. 6个顶点的无向图中，至少有（ A ）条边才能保证是一个连通图。A. 5 B. 6 C. 7 D. 865若某线性表中最常用的操作是删除第1个元素，则不宜采用（ D ）存储方式。A.单链表 B.双链表 C.单向循环链表 D.顺序表66在一棵完全二叉树的顺序存储方式中，若编号i的结点有右孩子，则其右孩子的编号为（ C ）。A. 2i B. 2i-1 C. 2i+1 D. i/267. 按照二叉树的定义，具有3个结点的二叉树有（ C ）种不同形态。A. 3 B. 4 C. 5 D. 668. 在长为n的顺序表中，删除第i个元素(1in+1)需要向前移动（ A ）个元素。A. n-i B. n-i+1 C. n-i-1 D. i69. 一个队的入队顺序是1、2、3、4、5，则此队的出队顺序为（ D ）。A. 5、4、3、2、1 B. 4、5、3、2、1C. 4、3、5、1、2 D. 1、2、3、4、570. 栈是一种特殊的线性表，其特殊性表现在（ B ）。A. 可以顺序存储 B.只能从端点进行插入和删除 C. 可以链式存储 D. 可以在任何位置进行插入和删除71. 一棵二叉树中，第k层上最多有（ B ）个结点。A. 2k B.2k-1 C.2k D.2k-172. 一棵有18个结点的二叉树，其高度最小为（ B ）层。A. 4 B. 5 C. 6 D. 1873.有向图中，所有顶点入度和是所有顶点出度和的（ B ）倍。A. 0.5 B. 1 C. 2 D. 4（二）填空题1.数据元素之间存在的相互关系称为 数据逻辑结构 。2.数据结构从逻辑上分为 线性结构 和 非线性结构。3.线性表的顺序存储结构称为 顺序表 。4.所有插入在表的一端进行，而所有删除在表的另一端进行的线性表称为 队列 。5.深度为h的二叉树,最少有 h 个结点。6.折半查找要求待查表为 顺序存储并有序的 表。7.n个记录按其关键字大小递增或递减的次序排列起来的过程称为 排序 。8.存储数据时,不仅要存储数据元素的值,还要存储元素之间的相互关系。9将一棵有100个结点的完全二叉树按层编号，则编号为49的结点X，其双亲PARENT（X）的编号为 24 。10、一个字符串相等的充要条件是 长度相等 和 对应位置字符相同 。11、在有向图的邻接表和逆邻接表表示中，每个顶点的边链表中分别链接着该顶点的所有 边 和顶点相邻的 结点。11、在一个长度为n 的顺序表中向第 i个元素（0n）的排好序的表归并成一个排好序的表，至少要进行 n 次键值比较。通常从四个方面评价算法的质量：_正确性_、_易读性_、_健壮性_和_高效性_。31、一个算法的时间复杂度为(n3+n2log2n+14n)/n2，其数量级表示为_O(n)_。32、若用链表存储一棵二叉树时，每个结点除数据域外，还有指向左孩子和右孩子的两个指针。在这种存储结构中，n个结点的二叉树共有_2n_个指针域，其中有_n-1_个指针域是存放了地址，有_n+1_个指针是空指针。33、对于一个具有n个顶点和e条边的有向图和无向图，在其对应的邻接表中，所含边结点分别有_e_个和_2e_个。34、在一个具有n个顶点的无向完全图中，包含有_n(n-1)/2_条边，在一个具有n个顶点的有向完全图中，包含有_ n(n-1)_条边。35、36.在快速排序、堆排序、归并排序中，_归并排序_排序是稳定的。36、37.中序遍历二叉排序树所得到的序列是_升序_序列。38.快速排序的最坏时间复杂度为_O(n2)_，平均时间复杂度为_O(nlog2n)_。39.设一组初始记录关键字序列为(55，63，44，38，75，80，31，56)，则利用筛选法建立的初始堆为_31，38，55，63，75，80，44，56_。40数据的物理结构主要包括_顺序_和_链式_两种情况。41.设一棵完全二叉树中有500个结点，则该二叉树的深度为_9_；若用二叉链表作为该完全二叉树的存储结构，则共有_501_个空指针域。42、设输入序列为1、2、3，则经过栈的作用后可以得到_5_种不同的输出序列。43、设有向图G用邻接矩阵Ann作为存储结构，则该邻接矩阵中第i行上所有元素之和等于顶点i的_出度_，第i列上所有元素之和等于顶点i的_入度_。设哈夫曼树中共有n个结点，则该哈夫曼树中有_0_个度数为1的结点。44、设有向图G中有n个顶点e条有向边，所有的顶点入度数之和为d，则e和d的关系为_e=2d_。45、_中序_遍历二叉排序树中的结点可以得到一个递增的关键字序列（填先序、中序或后序）。46、设查找表中有100个元素，如果用二分法查找方法查找数据元素X，则最多需要比较_7_次就可以断定数据元素X是否在查找表中。47、不论是顺序存储结构的栈还是链式存储结构的栈，其入栈和出栈操作的时间复杂度均为_O(1)_。48、设有n个结点的完全二叉树，如果按照从自上到下、从左到右从1开始顺序编号，则第i个结点的双亲结点编号为_i/2_，右孩子结点的编号为_2i+1_。49、设一组初始记录关键字为(72，73，71，23，94，16，5)，则以记录关键字72为基准的一趟快速排序结果为_5,16,71,23,72,94,73,_。50、设有向图G中有向边的集合E=，则该图的一种拓扑序列为_1,4,2,3_。51、下列算法实现在顺序散列表中查找值为x的关键字，请在下划线处填上正确的语句。struct recordint key; int others;int hashsqsearch(struct record hashtable ,int k)int i,j; j=i=k%p;while (hashtablej.key!=k&hashtablej.flag!=0)j=(_j+1) %m; if (i=j) return(-1); if (_hashtablej.key=k _ ) return(j); else return(-1); 52、下列算法实现在二叉排序树上查找关键值k，请在下划线处填上正确的语句。typedef struct nodeint key; struct node *lchild; struct node *rchild;bitree;bitree *bstsearch(bitree *t, int k) if (t=0 ) return(0);else while (t!=0)if (t-key=k)_ return(t)_; else if (t-keyk) t=t-lchild; else_ t=t-rchild _;53、设有n个无序的记录关键字，则直接插入排序的时间复杂度为_o(n2)_，快速排序的平均时间复杂度为_o(nlog2n)_。54、设指针变量p指向双向循环链表中的结点X，则删除结点X需要执行的语句序列为_p-llink-rlink=p-next;p-rlink-llink=p-llink;_（设结点中的两个指针域分别为llink和rlink）。根据初始关键字序列(19，22，01，38，10)建立的二叉排序树的高度为_ 3_。55、深度为k的完全二叉树中最少有_ 2k-1_个结点。56、设初始记录关键字序列为(K1，K2，Kn)，则用筛选法思想建堆必须从第_ n/2_个元素开始进行筛选。59、设哈夫曼树中共有99个结点，则该树中有_50_个叶子结点；若采用二叉链表作为存储结构，则该树中有_100_个空指针域。60、设有一个顺序循环队列中有M个存储单元，则该循环队列中最多能够存储_M_个队列元素；当前实际存储_M-1_个队列元素（设头指针F指向当前队头元素的前一个位置，尾指针指向当前队尾元素的位置）。61、设顺序线性表中有n个数据元素，则第i个位置上插入一个数据元素需要移动表中_N-i+1_个数据元素；删除第i个位置上的数据元素需要移动表中_n-i_个元素。62、设一组初始记录关键字序列为(20，18，22，16，30，19)，则以20为中轴的一趟快速排序结果为_19,18,_16,20,30,22_。63、设一组初始记录关键字序列为(20，18，22，16，30，19)，则根据这些初始关键字序列建成的初始堆为_16,18,19,20,30,22_。64、设无向图对应的邻接矩阵为A，则A中第i上非0元素的个数_等于_第i列上非0元素的个数（填等于，大于或小于）。65、设前序遍历某二叉树的序列为ABCD，中序遍历该二叉树的序列为BADC，则后序遍历该二叉树的序列为_BDCA_。66、设散列函数H(k)=k mod p，解决冲突的方法为链地址法。要求在下列算法划线处填上正确的语句完成在散列表hashtalbe中查找关键字值等于k的结点，成功时返回指向关键字的指针，不成功时返回标志0。typedef struct node int key; struct node *next; lklist; void createlkhash(lklist *hashtable )int i,k; lklist *s;for(i=0;im;i+)_ hashtablei=0_;for(i=0;ikey=ai;k=ai % p; s-next=hashtablek;_ hashtablek=s _;三、应用题主要考点1、二叉树的遍历与恢复（即已知二叉树对其遍历、已知遍历序列恢复二叉树）、哈夫曼树的构造2、图的存储结构（邻接矩阵、邻接表）、图的应用（最小生成树、拓扑排序）3、各种查找方法（二叉排序树、散列表、平均查找长度）4、各种排序方法四、算法设计题主要考点1、线性表的简单算法(顺序表和单链表的基本运算)。2、二叉树的简单应用算法(如二叉树的遍历、求二叉树的高度、二叉树中叶子节点数等)。3、查找算法（顺序查找、二分查找）。4、排序算法（如插入、交换、选择排序等）。