湖南大学(866)数据结构模拟题

2022年湖南大学计算机科学与技术专业《数据结构与算法》科目期末试卷A（有答案）一、选择题1、已知广义表LS=（（a，b，c），（d，e，f）），用head和tail数取出LS中原子e 的运算是（）。

A.head（tail（LS））B.tail（head（LS））C.head（tail（head（tail（LS））））D.head（tail（tail（head（LS））））2、下述文件中适合于磁带存储的是（）。

A.顺序文件B.索引文件C.哈希文件D.多关键字文件3、连续存储设计时，存储单元的地址（）。

A.一定连续B.一定不连续C.不一定连续D.部分连续，部分不连续4、已知有向图G=(V，E)，其中V={V1，V2，V3，V4，V5，V6，V7}， E=｛<V1，V2>，<V1，V3>，<V1，V4>，<V2，V5>，<V3，V5>， <V3，V6>，<V4，V6>，<V5，V7>，<V6，V7>｝，G的拓扑序列是（）。

A.V1，V3，V4，V6，V2，V5，V7B.V1，V3，V2，V6，V4，V5，V7C.V1，V3，V5，V2，V6，V7D.V1，V2，V5，V3，V4，V6，V75、下列关于AOE网的叙述中，不正确的是（）。

A.关键活动不按期完成就会影响整个工程的完成时间B.任何一个关键活动提前完成，那么整个工程将会提前完成C.所有的关键活动提前完成，那么整个工程将会提前完成D.某些关键活动若提前完成，那么整个工程将会提前完成6、已知字符串S为“abaabaabacacaabaabcc”，模式串t为“abaabc”，采用KMP算法进行匹配，第一次出现“失配”（s!＝t）时，i＝j＝5，则下次开始匹配时，i和j的值分别（）。

A．i＝1，j＝0 B．i＝5，j＝0 C．i＝5，j＝2 D．i＝6，j＝27、下列选项中，不能构成折半查找中关键字比较序列的是（）。

数据结构与算法模拟习题（附参考答案）一、单选题（共86题，每题1分，共86分）1.具有5个顶点的有向完全图有多少条弧？A、16B、20C、25D、10正确答案：B2.下列程序的时间复杂度为（）。

i = 0; s = 0;while(s < n){i++;s = s + i;}A、Θ(n)B、Θ(1)C、Θ(n2)D、Θ(n½)正确答案：D3.栈和队列的共同点是（）。

A、没有共同点B、只允许在端点处插入和删除元素C、都是先进后出D、都是先进先出正确答案：B4.下面描述中正确的为( )。

A、线性表的逻辑顺序与物理顺序总是一致的B、线性表的顺序存储表示优于链式存储表示。

C、线性表若采用链式存储表示时所有结点之间的存储单元地址可连续可不连续。

D、二维数组是其数组元素为线性表的线性表。

正确答案：C5.对N个不同的数据采用冒泡算法进行从大到小的排序，下面哪种情况下肯定交换元素次数最多？A、从大到小排好的B、元素无序C、元素基本有序D、从小到大排好的正确答案：D6.表达式3*2^(4+2*2-6*3)-5求值过程中当扫描到6时，对象栈和算符栈为（），其中^为乘幂。

A、3, 2, 8；( * ^ -B、3, 2, 4, 2, 2；( * ^ ( -C、3, 2, 4, 1, 1；( ^ ( + -D、3, 2, 8；( * ^ ( -正确答案：D7.二叉树的高度若根节点为高度1，一棵具有 1025 个结点的二叉树的高度为▁▁▁▁▁ 。

A、10～1024 之间B、11～1025 之间C、10D、11正确答案：B8.数据采用链式存储结构时，要求( )A、每个节点占用一片连续的存储区域B、所有节点占用一片连续的存储区域C、节点的最后一个数据域一定是指针类型D、每个节点有多少个后继就设多少个指针域正确答案：A9.在N个结点的顺序表中，算法的时间复杂度为O(1)的操作是：A、将N个结点从小到大排序B、删除第i个结点（1≤i≤N）C、访问第i个结点（1≤i≤N）和求第i个结点的直接前驱（2≤i≤N）D、在第i个结点后插入一个新结点（1≤i≤N）正确答案：C10.将元素序列{18, 23, 4, 26, 31, 33, 17, 39}按顺序插入一个初始为空的、大小为13的散列表中。

《数据结构》模拟试题13一、填空题（每小题2分，共18分）1、数据的逻辑结构包括，和三种结构。

2、队列是操作受限的线性结构，只能在插入元素，而在删除元素。

3、串是一种特殊的线性表，其特殊性体现在。

4、有一个10阶对称矩阵A，采用压缩存储方式采用压缩存储方式，以行为主存储下三角形到一个一维数组中，A[0][0]的地址是100（每个元素占2个基本存储单元），则A[5][9]的地址是。

5、在高度为h的二叉树的中只有度为0和度为2的结点，则该类二叉树中所包含的结点数至少为。

6、对于一个有n个顶点和e条边的无向图，若采用邻接链表存储，则表头向量的大小为，邻接表中的结点总数为。

7、对线性表进行二分查找时，要求线性表必须是，且要求。

8、对于文件，按物理结构划分，可分为顺序文件、文件、文件和多关键字文件。

9、外部排序的最基本方法是，其主要时间花费在方面。

二、单项选择题（请将答案写在题目后的括号中。

每题2分，共18分）1、如下函数是求1!+2!+…+n!，其时间复杂度是（）。

Long int Sum (int n){ long int sum=0 , t=1 ; int p ;for (p=1; p<=n ;p++) { t=t*p ; sum+=t ; }return(sum) ;}（A）O(n) （B）O(n2) （C）O(㏒2n) （D）O(n㏒2n)2、设有一个栈顶指针为top的顺序栈S，则弹出S的栈定元素的操作是（）。

（A）p=S[top++]；（B）p=S[++top]；(C)p=S[top--]；（D）p=S[--top]；3、广义表((a),((b),c),(((d))))的表头是，表尾是。

（）（A）(a) ((b),c),(((d))) （B）(a) (((b),c),(((d))))（C）((a),((b),c)),(((d))) （D）(a) (((d)))4、一棵二叉树，其先序遍历序列是abdgehicf，中序遍历序列是gdbheiafc，则其后序遍历序列是( )。

试卷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时，经过（ ）次比较后查找成功。

《数据结构》模拟试题一、单项选择题(30分)1 .在数据结构的讨论中把数据结构从逻辑上分为 ____ J 。

A.内部结构与外部结构B.静态结构与动态结构C.线性结构与非线性结构D.紧凑结构与非紧凑结构。

2 .算法分析的两个主要方面是―DA.正确性和简明性B.可读性和文档性C.数据复杂性和程序复杂性D.空间复杂性和时间复杂性 3 .在存储数据时，通常不仅要存储各数据元素的值，而且还要存储 B 。

A.数据的处理方法B.数据元素的类型C.数据元素之间的关系D.数据的存储方法4 .设顺序表有9个元素，则在第3个元素前插入一个元素所需移动元素的个数为cA.5B.6C.7D.95 .线性表采用链式存储结构时，要求内存中可用存储单元的地址—d _。

A.必须是连续的B.必须是部分连续的C. 一定是不连续的D.连续和不连续都可以6 .对具有n 个结点的线性表进行插入和删除操作，所需的算法时间复杂度为―dA. O(1)B. O(n)C. O(nlog 2n)D. O(n 2)7 .在单链表中指针p 所指结点之后插入指针为s 的结点，正确的操作是_b ___ 。

A. p->next=s;s->next= p->next;B. s->next= p->next; p->next=s;C. p->next=s; p->next = s->nextD. p->next=s->next; p->next=s;8 .栈中元素的进出原则是■—bA.先进先出B.先进后出C.栈空则进D.栈满则出 9 .长度是n 的顺序循环队列，front 和rear 分别指示队首和队尾，判断队列为满队列的条件是_dB. front=0 10 .下面说法不正确的是 ___ c. A.广义表的表头总是一个广义表 B.广义表的表尾总是一个广义表C.广义表难以用顺序存储结构D.广义表可以是一个多层次的结构 A. rear=0C. rear==frontD. (rear+1) %n==front11.已知二叉树的先序遍历序列为ABCD,中序遍历序列为BCDA,则后序遍历序列为—d—。

《数据结构》模拟试卷及参考答案模拟试卷一一、单选题（每题2 分，共20分）1.以下数据结构中哪一个是线性结构？( )A. 有向图B. 队列C. 线索二叉树D. B树2.在一个单链表HL中，若要在当前由指针p指向的结点后面插入一个由q指向的结点，则执行如下( )语句序列。

A. p=q; p->next=q;B. p->next=q; q->next=p;C. p->next=q->next; p=q;D. q->next=p->next; p->next=q;3.以下哪一个不是队列的基本运算？（）A. 在队列第i个元素之后插入一个元素B. 从队头删除一个元素C. 判断一个队列是否为空D.读取队头元素的值4.字符A、B、C依次进入一个栈，按出栈的先后顺序组成不同的字符串，至多可以组成( )个不同的字符串？A.14B.5C.6D.85.由权值分别为3,8,6,2的叶子生成一棵哈夫曼树，它的带权路径长度为( )。

以下6-8题基于图1。

6.该二叉树结点的前序遍历的序列为( )。

A.E、G、F、A、C、D、BB.E、A、G、C、F、B、DC.E、A、C、B、D、G、FD.E、G、A、C、D、F、B7.该二叉树结点的中序遍历的序列为( )。

A. A、B、C、D、E、G、FB. E、A、G、C、F、B、DC. E、A、C、B、D、G、FE.B、D、C、A、F、G、E8.该二叉树的按层遍历的序列为( )。

A．E、G、F、A、C、D、B B. E、A、C、B、D、G、FC. E、A、G、C、F、B、DD. E、G、A、C、D、F、B9.下面关于图的存储的叙述中正确的是( )。

A．用邻接表法存储图，占用的存储空间大小只与图中边数有关，而与结点个数无关B．用邻接表法存储图，占用的存储空间大小与图中边数和结点个数都有关C. 用邻接矩阵法存储图，占用的存储空间大小与图中结点个数和边数都有关D．用邻接矩阵法存储图，占用的存储空间大小只与图中边数有关，而与结点个数无关10.设有关键码序列(q，g，m，z，a，n，p，x，h)，下面哪一个序列是从上述序列出发建堆的结果?( )A. a，g，h，m，n，p，q，x，zB. a，g，m，h，q，n，p，x，zC. g，m，q，a，n，p，x，h，zD. h，g，m，p，a，n，q，x，z二、填空题（每空1分，共26分）1.数据的物理结构被分为_________、________、__________和___________四种。

数据结构模拟考试（总分100分，考试时长90分钟）一、单项选择题（每小题2 分，共 100分）1、一棵具有 n 个结点的完全二叉树的树高度(深度)是( A )A、「log2n」+1B、log2n+1C、「log2n」D、log2n-12、若长度为n的线性表采用顺序存储结构,在其第i个位置插入一个新元素的算法的时间复杂度为A、O(n)B、O(0)C、O(1)D、O(n^2)3、一个顺序栈S,空栈时top的初始值为0,其栈顶指针为top,则将元素e入栈的操作是( )。

A、*S->top=e;S->top++;B、S->top++;*S->top=e;C、*S->top=eD、S->top=e;4、下列几种排序方法中要求辅助空间最大的是( )A、堆排序B、直接选择排序C、归并排序D、快速排序5、给定排序码值序列为{F，B，J，C，E，A，I，D，C，H}，对其按字母的字典序列的次序进行排列，冒泡排序(大数下沉)的第一趟排序结果应为A、{B，F，C，J，A，E，D，I，C，H}B、{C，B，D，A，E，F，I，C，J，H}C、{B，F，C，E，A，I，D，C，H，J}D、{A，B，D，C，E，F，I，J，C，H}6、对含有 10 个数据元素的有序查找表执行折半查找,当查找失败时,至少需要比较( )次。

A、2B、3C、4D、57、数组Ｑ［ｎ］用来表示一个循环队列，ｆ为当前队列头元素的前一位置，ｒ为队尾元素的位置，假定队列中元素的个数小于ｎ，计算队列中元素个数的公式为（）。

A、r-fB、(n+f-r)%nC、n+r-fD、（n+r-f)%n8、若长度为 n 的线性表采用顺序存储结构，访问其第 i 个元素的算法时间复杂度为（）A、0 ( 1 )B、0 ( n )C、0 ( n2 )D、0 ( log2n )9、(6分)若希望1000个无序元素中尽快求得前10个最大元素,应借用(A)。

《数据结构与算法分析》课程模拟试卷及答案一、选择题（每题2分，共20分）1. 下面哪个不是线性结构的基本特征？A. 有且只有一个根结点B. 每个结点最多有一个前驱，最多有一个后继C. 至少有一个结点D. 以任意一个结点为根，都可以将结构转换为树形结构答案：D2. 下面关于栈的叙述中，正确的是（）。

A. 栈是一种先进先出的线性表B. 栈是一种先进后出的线性表C. 栈是一种只能在一端插入和删除的线性表D. 栈是一种只能在一端插入和删除的有序表答案：B3. 在长度为n的线性表中，删除第i个元素（1≤i≤n）的时间复杂度是（）。

A. O(1)B. O(n)C. O(n^2)D. O(logn)答案：B4. 下面关于队列的叙述中，正确的是（）。

A. 队列是一种先进先出的线性表B. 队列是一种先进后出的线性表C. 队列是一种只能在一端插入和删除的线性表D. 队列是一种只能在一端插入和删除的有序表答案：A5. 下面哪一个不是排序算法稳定性的必要条件？A. 相同值的元素在排序前后保持原有的相对顺序B. 相同值的元素在排序过程中不发生交换C. 排序算法的时间复杂度为O(nlogn)D. 排序算法的空间复杂度为O(1)答案：C二、填空题（每题3分，共15分）6. 在二叉树中，每个结点的度是指结点的子树个数。

度为0的结点称为______结点。

答案：叶子7. 在二叉树的顺序存储结构中，若结点n的左孩子是2n，则结点n的右孩子是______。

答案：2n+18. 快速排序算法的时间复杂度为______。

答案：O(nlogn)9. 在单链表中，要删除指针p所指的结点，需要执行的操作是______。

答案：p->next = p->next->next10. 堆排序的时间复杂度为______。

答案：O(nlogn)三、简答题（每题10分，共30分）11. 请简述二分查找算法的基本思想。

答案：二分查找算法的基本思想是：首先将待查找的元素与有序数组的中间元素进行比较，若相等则查找成功；若待查找的元素小于中间元素，则在数组的左半部分继续查找；若待查找的元素大于中间元素，则在数组的右半部分继续查找。

数据结构模考试题及答案一、单选题（共100题，每题1分，共100分）1、下面关于生成树的描述中，不正确的是( )A、生成树是树的一种表现形式B、生成树一定是连通的C、生成树一定不含有环D、若生成树顶点个数为n，则其边数一定为n-1正确答案：A2、用邻接表表示图进行广度优先遍历时，通常是采用（）来实现算法的。

A、图B、栈C、队列D、树正确答案：C3、下列四种基本的逻辑结构中，结构结点间不存在任何逻辑联系的是（）A、集合B、树形结构C、图形结构D、线性结构正确答案：A4、以下数据结构中，哪一个是线性结构（）。

A、线索二叉树B、二叉树C、有向图D、串正确答案：D5、n个顶点的连通图至少中含有( )边。

A、n-1B、n+1C、nD、0正确答案：A6、G是一个非连通无向图，共有28条边，则该图至少有( )个顶点。

A、7B、8C、6D、9正确答案：D7、在一个链队列中，假定front和rear分别为队首和队尾指针，则删除一个结点的操作为（）。

A、rear=front->nextB、front=rear->nextC、front=front->nextD、rear=rear->next正确答案：C8、一个栈的输入序列是 1 2 3 4 5，则下列序列中是栈的输出序列的是（）。

A、1,4,2,5,3B、3,1,2,4,5C、2,3,4,1,5D、5,4,1,3,2正确答案：C9、假设以数组A[m]存放循环队列的元素。

已知队列的长度为length，指针rear指向队尾元素的下一个存储位置，则队头元素所在的存储位置为( )A、(rear-length+m+1)％mB、(rear-length+m)％mC、(rear-length+m-1)％mD、(rear-length)％m正确答案：B10、与数据元素本身的形式、内容、相对位置、个数无关的是数据的（）。

A、存储结构B、操作C、逻辑结构D、算法正确答案：C11、深度为k的完全二叉树中最少有（）个结点。