2数据结构试卷a答案

中国矿业大学2011-2012学年《数据结构》试卷（A卷）（考试时间：100分钟）一. 填空（每空2分，共40分）1. 数据结构式具有相同性质的数据元素的（1）。

2. 通常程序在调用另一个程序时，都需要使用一个（2）来保存被调用程序内分配的局部变量、形式参数的存储空间以及返回地址。

3. 有6行8列的二维数组A，每个元素用相邻的6个字节存储，存储器按字节编址，已知A的起始存储地址（基址）为1000，在行优先存储和列优先存贮情况下A[5,5]的存储地址分别为__（3）_____,_____(4)____。

4. 完全二叉树第4 个节点的父节点是第 (5) 节点，左孩子是第 (6) 个节点。

如果该二叉树有10层，则共有 (7) 个节点。

5. 请描述在循环队列Q中，队头和队尾指针分别由front和rear表示，该队列有10个存储空间，判断队空和队满的条件分别分：_____(8)________,_______(9)_________。

6. 字符串t=”child”，s=”cake”，请写出下列函数的结果：StrLength(t) =（10）__;Concat(SubString(s,3,1)，SubString(t,2,2))=____（11）___。

7. 一棵二叉树为则后序序列为（12），中序序列为（13），先序序列为__（14）____。

8. 请用数据序列{53，17，12，66，58，70，87，25，56，60 }构造一棵二叉排序树_(15）_。

9.。

一个栈输入的序列式1,2,3，则可能的且以2为开头的输出序列是 (16) ，不可能的序列是____（17）____。

10. 有n个结点的无向完全图的边数分别为_______(18)_______。

11. 要从数据：2，3，4，8，9，11，13查找11，若采用折半查找法，则在（19）次比较后，才找到该数据。

12. 在直接插入排序、希尔排序、冒泡排序和快速排序中，平均情况下（20）_____最快。

数据结构试卷（二）一、选择题(24分)1．下面关于线性表的叙述错误的是（）。

(A) 线性表采用顺序存储必须占用一片连续的存储空间(B) 线性表采用链式存储不必占用一片连续的存储空间(C) 线性表采用链式存储便于插入和删除操作的实现(D) 线性表采用顺序存储便于插入和删除操作的实现2．设哈夫曼树中的叶子结点总数为m，若用二叉链表作为存储结构，则该哈夫曼树中总共有（）个空指针域。

(A) 2m-1 (B) 2m (C) 2m+1 (D) 4m3．设顺序循环队列Q[0：M-1]的头指针和尾指针分别为F和R，头指针F总是指向队头元素的前一位置，尾指针R总是指向队尾元素的当前位置，则该循环队列中的元素个数为（）。

(A) R-F (B) F-R (C) (R-F+M)％M (D) (F-R+M)％M4．设某棵二叉树的中序遍历序列为ABCD，前序遍历序列为CABD，则后序遍历该二叉树得到序列为（）。

(A) BADC (B) BCDA (C) CDAB (D) CBDA5．设某完全无向图中有n个顶点，则该完全无向图中有（）条边。

(A) n(n-1)/2 (B) n(n-1) (C) n2(D) n2-16．设某棵二叉树中有2000个结点，则该二叉树的最小高度为（）。

(A) 9 (B) 10 (C) 11 (D) 127．设某有向图中有n个顶点，则该有向图对应的邻接表中有（）个表头结点。

(A) n-1 (B) n (C) n+1 (D) 2n-18．设一组初始记录关键字序列(5，2，6，3，8)，以第一个记录关键字5为基准进行一趟快速排序的结果为（）。

(A) 2，3，5，8，6 (B) 3，2，5，8，6(C) 3，2，5，6，8 (D) 2，3，6，5，8二、填空题(24分)1.为了能有效地应用HASH查找技术，必须解决的两个问题是____________________和__________________________。

石家庄学院《数据结构》期末考试试卷(A 卷)题目部分，（卷面共有135题，100分，各大题标有题量和总分）一、应用题（4小题，共8分）1．试列出下图全部可能的拓扑排序序列2．在实现快速排序的非递归算法时，可根据基准对象，将待排序排序码序列划分为两个子序列。

若下一趟首先对较短的子序列进行排序，试证明在此做法下，快速排序所需要的栈的深度为O(log2n)。

3．设有上三角矩阵(aij)n*n ，将其上三角中的元素按先行后列的顺序存于数组B （1:m ）中，使得B[k]= aij 且k=f1(i)+f2(j)+c ，请推导出函数f1,f2和常数c ，要求f1和f2中不含常数项。

4．用三元数组表示稀疏矩阵的转置矩阵,并简要写出解题步骤。

二、判断正误（20小题，共10分）1．散列表的结点中包含数据元素自身的信息，不包含任何指针。

(F)2．负载因子（装填因子）是散列表的一个重要参数，它反映敞列表的装满程度。

( T )3．一个图的广度优先搜索树是唯一的。

( F )4．外排序过程主要分为两个阶段：生成初始归并段和对归并段进行逐趟归并的阶段。

（ T ） 5．在完成外排序过程中，每个记录的I/O 次数必定相等。

( F )6．为提高在外排序过程中，对长度为N 的初始序列进行“置换—选择”排序时，可以得到的最大初始有序段的长度不超过N/2。

( F )7．在外部排序时，利用选择树方法在能容纳m 个记录的内存缓冲区中产生的初始归并段的平均长度为2m 个记录。

( T )8．堆排序是稳定的排序方法。

（ F ）9．循环队列通常用指针来实现队列的头尾相接。

（ F ） 10．有n 个数顺序(依次)进栈，出栈序列有c n 种，即：21(2)!1(!)n n C n n =⨯+。

（ T ） 11．顺序存储方式的优点是存储密度大，且插入、删除运算效率高。

( F )12．完全二叉树的某结点若无左孩子，则它必是叶结点。

（ T ） 13．深度为K 的二叉树中结点总数≤2k-1。

东北大学继续教育学院数据结构II 试卷（作业考核线上1） A 卷学习中心：院校学号：姓名（共 6 页）[A ]1．抽象数据类型的三个组成部分分别为A．数据对象、数据关系和基本操作B．数据元素、逻辑结构和存储结构C．数据项、数据元素和数据类型D．数据元素、数据结构和数据类型[B ]2．要求相同逻辑结构的数据元素具有相同的特性，其含义为A. 数据元素具有同一的特点B. 不仅数据元素包含的数据项的个数相同，而且其对应数据项的类型要一致C. 每个数据元素都一样D. 仅需要数据元素包含的数据项的个数相同[D ]3．下列各式中，按增长率由小至大的顺序正确排列的是A．，n！，2n ，n3/2B．n3/2，2n，n logn，2100C．2n，log n，n logn，n3/2D．2100，logn, 2n, n n[B ]4. 在下列哪种情况下，线性表应当采用链表表示为宜A.经常需要随机地存取元素B.经常需要进行插入和删除操作C.表中元素需要占据一片连续的存储空间D.表中元素的个数不变[C ]5．设指针p指向双链表的某一结点，则双链表结构的对称性是A. p->prior->next=p->next->next;B. p->prior->prior=p->next->prior;C. p->prior->next=p-> next->prior;D. p->next->next= p->prior->prior;[ D]6. 已知指针p和q分别指向某带头结点的单链表中第一个结点和最后一个结点。

假设指针s指向另一个单链表中某个结点，则在s所指结点之后插入上述链表应执行的语句为A. s->next=q；p->next=s->next；B. s->next=p；q->next=s->next；C. p->next=s->next；s->next=q；D. q->next=s->next；s->next=p；[A ]7. 栈和队列的共同特点是A.只允许在端点处插入和删除元素B.都是先进后出C.都是先进先出D.没有共同点[D ]8. 对于链队列，在进行插入运算时.A. 仅修改头指针B. 头、尾指针都要修改C. 仅修改尾指针D.头、尾指针可能都要修改[B ]9．设有一个顺序栈的入栈序列是1、2、3，则3个元素都出栈的不同排列个数为A．4 B．5 C. 6 D. 7[D ]10．设一个栈的输入序列为A，B，C，D，则借助一个栈所得到的输出序列不可能是A．A，B，C，D B．D，C，B，AC. A，C，D，BD. D，A，B，C[C ]11．表达式a*(b+c)-d的后缀表达式是A．abcd*+- B．abc*+d- C．abc+*d- D．-+*abcd[B ]12．某二叉树的先序序列和后序序列正好相反，则该二叉树的特点一定是A. 空或只有一个结点B.高度等于其结点数C. 任一结点无左孩子D.任一结点无右孩子[B ]13．下面的说法中正确的是(1)任何一棵二叉树的叶子结点在种遍历中的相对次序不变。

数据结构试卷（一）一、选择题(30分)1．设一维数组中有n个数组元素，则读取第i个数组元素的平均时间复杂度为（）。

(A) O(n)(B) O(nlog2n)(C) O(1)(D) O(n2)2．设一棵二叉树的深度为k，则该二叉树中最多有（）个结点。

(A) 2k-1(B) 2k(C) 2k-1(D) 2k-13．设某无向图中有n个顶点e条边，则该无向图中所有顶点的入度之和为（）。

(A) n(B) e(C) 2n(D) 2e4．在二叉排序树中插入一个结点的时间复杂度为（）。

(A) O(1)(B) O(n)(C) O(log2n)(D) O(n2)5．设某有向图的邻接表中有n个表头结点和m个表结点，则该图中有（）条有向边。

(A) n(B) n-1(C) m(D) m-16．设一组初始记录关键字序列为(345，253，674，924，627)，则用基数排序需要进行（）趟的分配和回收才能使得初始关键字序列变成有序序列。

(A) 3(B) 4(C) 5(D) 87．设用链表作为栈的存储结构则退栈操作（）。

(A) 必须判别栈是否为满(B) 必须判别栈是否为空(C) 判别栈元素的类型(D) 对栈不作任何判别8．下列四种排序中（）的空间复杂度最大。

(A) 快速排序(B) 冒泡排序(C) 希尔排序(D) 堆9．设某二叉树中度数为0的结点数为N0，度数为1的结点数为N l，度数为2的结点数为N2，则下列等式成立的是（）。

(A) N0=N1+1(B) N0=N l+N2(C) N0=N2+1(D) N0=2N1+l10.设有序顺序表中有n个数据元素，则利用二分查找法查找数据元素X的最多比较次数不超过（）。

(A) log2n+1(B) log2n-1(C) log2n(D) log2(n+1)二、填空题(42分)1．1．设有n个无序的记录关键字，则直接插入排序的时间复杂度为________，快速排序的平均时间复杂度为_________。

数据结构试题一、单选题（每题 2 分，共20分）1.1. 对一个算法的评价，不包括如下（ B ）方面的内容。

A．健壮性和可读性B．并行性 C．正确性 D．时空复杂度2.2. 在带有头结点的单链表HL中，要向表头插入一个由指针p指向的结点，则执行( A )。

A. p->next=HL->next; HL->next=p;B. p->next=HL; HL=p;C. p->next=HL; p=HL;D. HL=p; p->next=HL;3.3. 对线性表，在下列哪种情况下应当采用链表表示？( B )A.经常需要随机地存取元素B.经常需要进行插入和删除操作C.表中元素需要占据一片连续的存储空间D.表中元素的个数不变4.4. 一个栈的输入序列为 1 2 3，则下列序列中不可能是栈的输出序列的是( C )A. 2 3 1B. 3 2 1C. 3 1 2D. 1 2 35.5. AOV网是一种（ D ）。

A．有向图 B．无向图 C．无向无环图D．有向无环图6.6. 采用开放定址法处理散列表的冲突时，其平均查找长度（ B ）。

A．低于链接法处理冲突 B. 高于链接法处理冲突C．与链接法处理冲突相同 D．高于二分查找7.7. 若需要利用形参直接访问实参时，应将形参变量说明为（ D ）参数。

A．值 B．函数 C．指针 D．引用8.8. 在稀疏矩阵的带行指针向量的链接存储中，每个单链表中的结点都具有相同的（ A ）。

A．行号B．列号 C．元素值 D．非零元素个数9.9. 快速排序在最坏情况下的时间复杂度为（ D ）。

A．O(log2n) B．O(nlog2n) C．O(n) D．O(n2)10.10. 从二叉搜索树中查找一个元素时，其时间复杂度大致为( C )。

A. O(n)B. O(1)C. O(log2n) D. O(n2)二、运算题（每题 6 分，共24分）1. 1. 数据结构是指数据及其相互之间的_对应关系(联系)。

数据结构期末考试试题（含答案）2005年－2006学年第⼆学期“数据结构”考试试题（A）姓名学号(序号)_答案隐藏班号要求：所有的题⽬的解答均写在答题纸上（每张答题纸上要写清楚姓名、班号和学号），需写清楚题⽬的序号。

每张答题纸都要写上姓名和序号。

⼀、单项选择题（每⼩题2分，共20分）1．数据的运算a 。

A.效率与采⽤何种存储结构有关B.是根据存储结构来定义的C.有算术运算和关系运算两⼤类D.必须⽤程序设计语⾔来描述答：A。

2.链表不具备的特点是 a 。

A.可随机访问任⼀结点B.插⼊删除不需要移动元素C.不必事先估计存储空间D.所需空间与其长度成正⽐答：参见本节要点3。

本题答案为：A。

3.在顺序表中删除⼀个元素的时间复杂度为 c 。

A.O(1)B.O(log2n)C.O(n)D.O(n2)答：C。

4．以下线性表的存储结构中具有随机存取功能的是d 。

A.不带头结点的单链表B.带头结点的单链表C.循环双链表D.顺序表解D。

5.⼀个栈的进栈序列是a，b，c，d，e，则栈的不可能的输出序列是c 。

A.edcba B.decbaC.dceabD.abcde答：C。

6.循环队列qu的队空条件是 d 。

A. (qu.rear+1)%MaxSize==(qu.front+1)%MaxSizeB. (qu.rear+1)%MaxSize==qu.front+1C.(qu.rear+1)%MaxSize==qu.frontD.qu.rear==qu.front答：D。

7.两个串相等必有串长度相等且 b 。

A.串的各位置字符任意B.串中各位置字符均对应相等C.两个串含有相同的字符D.两个所含字符任意答：B。

8.⽤直接插⼊排序对下⾯四个序列进⾏递增排序，元素⽐较次数最少的是c 。

A.94,32,40,90,80,46,21,69B.32,40,21,46,69,94,90,80C.21,32,46,40,80,69,90,94D.90,69,80,46,21,32,94,40答：C。

2003-2004学年第二学期数据结构期终试卷（A卷）（考试时间100分钟）班级姓名学号得分一、单项选择题（本大题共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]的地址为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 04 -20 05学年第2 学期《数据结构》期末考试试卷（A卷）一、单项选择（在备选答案中选出一个正确答案，并将其号码填在题后的括号内。

每题2分，共20分）01．堆是一种数据结构, ( ) 是堆.A、(10,50,80,30,60,20,15,18)B、(10,18,15,20,50,80,30,60)C、(10,15,18,50,80,30,60,20)D、(10,30,60,20,15,18,50,80)02．广义表有两个重要的基本操作,取列表表头Head(Ls) ,和取列表表尾Tail(Ls),请利用这两个操作取出Ls中原子f的运算是( ),已知广义表Ls=((a,b,c,d),(e,f,g,h)).A、Head(Tail(Ls))B、Tai(Head(Ls))C、. Head(Tail(Head(Tail(Ls))))D、Head(Tail(Tai(Head(Ls))))03.若已知一棵二叉树的前序序列是BEFCGDH,中序序列是FEBGCHD,则他的后序序列是( )A、EFGHBCDB、FEGHDCBC、FEGBHDCD、EFBGCHD04.在下列常用内部排序方法中属于不稳定排序的是( )A、希尔排序,快速排序,简单选择排序,堆排序B、希尔排序,快速排序,2-路归并排序,堆排序C、直接插入排序,起泡排序, 希尔排序, 简单选择排序D、2-路归并排序,堆排序, 希尔排序, 起泡排序05.有一个具有n个顶点的连通图生成的最小生成树中,具有( )条边A、nB、n-1C、n+1D、2n-106. 下面的二叉树中，（）不是平衡二叉树。

A B C D07.如下图给出由七个顶点组成的无向图,从顶点1出发,对它进行深度优先遍历得到的顶点序列是( )A、1354267 ①②B、1347625C、1534276 ③④⑦D、1247653⑤⑥.08. 将pascal语言的数组A[0..8,0..8]按行优先次序存储在起始地址为1000的连续的内存单元中，每个存储单元的长度为2，则元素A[7,3]的地址是( )A、1132B、1134C、1114D、111209.依次读入数据元素序列{a,b,c,d,e,f}进栈,每进一个元素机器可要求下一个元素进栈和出栈.如此进行,则栈空时弹出的元素构成的序列不可能出现( )A、{c,d,b,e,f,a}B、{d,c,e,b,f,a}C、{b,d,c,e,a,f}D、{b,e,d,a,c,f}10.从具有n 个结点的二叉排序树中查找一个元素时,在最坏情况下的时间复杂度为( )A、0(n)B、0(1)C、0(logn)D、O(n²)二、填空题（每空2分，共20分）1.对于双向链表,在两个结点之间插入一个新结点时需要修改的指针共有____个。

数据结构试卷（一)一、选择题(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.设线性表中有n个数据元素，则在顺序存储结构上实现顺序查找的平均时间复杂度为___________，在链式存储结构上实现顺序查找的平均时间复杂度为___________。

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

陕西科技大学试题纸（A参考答案及评分标准）课程数据结构班级信息、数学05学号姓名请在每小题的四个备选答案中，选出一个正确的答案，并将其号码填在括号内。

1.设一个栈的输入序列为1，2，3，4，则借助一个栈所得的输出序列不可能是（D）。

A．1，2，3，4 B．4，3，2，1C．1，3，4，2 D．4，1，2，32. 设有80行的二维数组A[80][60]，其元素长度为4字节，按行优先顺序存储，基地址为300，则元素A[18][25]的存储地址为（D）。

A．3800 B．4376 C．3900 D．47203. 将一棵有100个节点的完全二叉树从根这一层开始，每一层上从左到右依次对结点进行编号，根节点的编号为0，则编号为49的结点的左孩子编号为（B）。

A．98 B．99 C．50 D．494. 在长度为n的顺序存储的线性表中，删除第i个元素（1≤i ≤n）时，需要从前向后依次前移（A）个元素。

A．n-i B．n-i+1 C．n-i-1 D．i5. 栈的插入和删除操作在（A）进行。

A．栈顶B．栈底C．任意位置D．指定位置6. 链表适用于（A）查找。

A．顺序B．二分法C．二分法、顺序D．随机7. 深度为6(根结点的层次为1)的二叉树至多有（D）个结点。

A．64 B．32 C．31 D．638. 用邻接表表示图进行广度优先遍历时，通常是采用（B）来实现算法的。

A．栈B．队列C．树D．图9. 设有两个串ｐ和ｑ，求ｑ在ｐ中首次出现的位置的运算称作（B）。

A．连接B．模式匹配C．求子串D．求串长10.若某线性表中最常用的操作是取第i个数据元素，则采用（D）存储方式最节省时间。

A．单链表B．双链表C．单向循环D．顺序表11.三个结点可构成（D）个不同形态的二叉树。

A．2 B．3 C．4 D．512.下列关键字序列中，（D）是堆。

A．16,72,31,23,94,53 B．94,23,31,72,16,53C．16,53,23,94,31,72 D．16,23,53,31,94,7213.把一棵树转换为二叉树后，这棵二叉树的形态是（A）。

模拟试题二模拟试题二一、选择题（28分）1.设一数列的顺序为l，2，3,4，5,通过栈结构不可能排成的顺序数列为( )。

A)3,2，5，4，l B)1，5,4，2，3C）2，4，3,5,l D）4，5，3，2,l2。

二叉树的第3层最少有（)个结点。

A)0 B）1 C)2 D）33。

—个n个顶点的连通无向图，其边的个数至少为( )。

A) n-l B)n C）n+l D）nlogn4。

下列排序方法中，( ）的比较次数与记录的初始排列状态无关。

A）直接插入排序 B）起泡排序C）快速排序 D）直接选择排序5.-棵哈夫曼树总共有II个结点，则叶子结点有( ）个。

A）5 B）6 C）7 D)96.已知某算法的执行时间为（n+n2)+log2(n+2)，n为问题规模,则该算法的时间复杂度是( ）。

A)O（n）B）O（n2) C）O（log2n）D）O(nlog2n)7。

如果一棵树有10个叶子结点，则该树总共至少有( )个结点。

A）lO B）11 C）19 D) 218。

—个100×100的三角矩阵a采用行优先压缩存储后，如果首元素a[0]［0]是第一个元素，那么a[4] [2］是第( )个元素。

A）13 B) 401 C) 402 D）4039.有一棵二叉树如题图1,该树是（）。

A）二叉平衡树B)二叉排序树C)堆的形状D)以上都不是10。

对于含有n个顶点e条边的无向连通图，利用Prim算法生成最小代价生成树，其时间复杂度为（)，利用Kruska算法的时间复杂度为（).A）O（log2n) B）0(n2) C)O（ne) D）O（elog2ne)11.具有n个顶点的完全有向图的边数为( ）.A）n（n—l)/2 B）n（n-l） C) n2 D）n2—112。

设有100个元素，用折半查找时,最大比较次数为（)，最小比较次数为（）。

A）25 B)7 C) 10 D)l13。

在内部排序中，排序时不稳定的有（).A）插入排序B）冒泡排序C）快速排序D）归并排序14.串是一种特殊的线性表，其特殊性体现在（)。

数据结构（A卷）【含答案】试卷编号拟题教研室（或教师）签名教研室主任签名………………………………………………………………………………………………………课程名称（含档次）数据结构A课程代号课程编号专业层次（本、专）本科考试⽅式（开、闭卷）闭卷⼀、应⽤题(3⼩题,共20分)1.设有⼀个栈，元素进栈的次序为：A，B，C，D，E，⽤I表⽰进栈操作，O表⽰出栈操作，设初始状态栈为空，写出下列出栈的操作序列。

（8分）（1）C，B，A，D，E（2）A，C，B，E，D2. ⼀份电⽂中有6种字符：A,B,C,D,E,F，它们的出现频率依次为16，5，9，3，30，1，完成问题：（1）设计⼀棵哈夫曼树；（画出其树结构）（2）计算其带权路径长度WPL。

（8分）3. 已知⽆向图G的邻接表如图所⽰，分别写出从顶点1出发的深度遍历和⼴度遍历序列。

（4分）⼆、判断正误(10⼩题,共20分)1．顺序表结构适宜于进⾏顺序存取，⽽链表适宜于进⾏随机存取。

( )2．⼀个栈的输⼊序列为：A，B，C，D，可以得到输出序列：C，A，B，D。

( )3．栈和队列都是受限的线性结构。

（）4. 逻辑结构与数据元素本⾝的内容和形式⽆关。

（）5．线性表链式存储的特点是可以⽤⼀组任意的存储单元存储表中的数据元素。

（）6. 完全⼆叉树的某结点若⽆左孩⼦，则它必是叶结点。

（）7. 邻接表只能⽤于存储有向图，⽽邻接矩阵则可存储有向图和⽆向图。

（）8. 图的深度优先搜索序列和⼴度优先搜索序列不是惟⼀的。

（）9. 折半查找只适⽤于有序表，包括有序的顺序表和链表。

（）10. 每种数据结构都具备三个基本操作：插⼊、删除和查找。

（）三、单项选择题(15⼩题,共30分)1.算法分析的两个主要⽅⾯是（）。

A. 空间复杂度和时间复杂度B.正确性和简单性C.可读性和⽂档性D.数据复杂性和程序复杂性2.具有线性结构的数据结构是（）。

A.图B.树C.⼴义表D.栈3.下⾯程序段的时间复杂度是（）。

2011～2012学年第 1 学期期末考试试卷（A 卷）课程名称： 数据结构 任课教师姓名：卷面总分： 100 分 考试时长： 100 分钟 考试类别：闭卷 院（系）： 专 业： 年级： 2010 姓 名： 学 号：阅卷教师（签字）：一、 单项选择题（每题2分，共10题20分）1．以下那一个术语与数据的存储结构无关？ 。

A ．栈 B ．哈希表 C ．线索树D ．双向链表2．链表不具有的特点是 。

A ．插入、删除不需要移动元素B ．可随机访问任一元素C ．不必事先估计存储空间D ．所需空间与线性表长度成正比3．算术表达式a+b*（c+d/e ）转为后缀表达式后为 。

A ．ab+cde/* B ．abcde/+*+ C ．abcde/*++ D ．abcde*/++4．二维数组A[10][20]采用列优先的存储方法,若每个元素占2个存储单元，设A[0][0]的地址为100，则元素A[7][6]的存储地址为 。

A ．232B ．234C ．390D ．392装订线5．若一棵二叉树具有10 个度为2 的结点，5 个度为1 的结点，则度为0 的结点个数是 B 。

A．9 B．11 C．15 D．不确定6．一棵二叉树中序序列为FEABDC，后序序列为FBADCE，则层序序列为 D 。

A. ABCDEFB. EFCDBAC. FECDABD.7．在有向图G的是 D 。

A．G 中有弧<Vi，Vj>B．G 中有一条从Vi 到Vj 的路径C．G 中没有弧<Vi,Vj>D．G 中有一条从Vj 到Vi 的路径8．对于二叉排序树，下面的说法 C 是正确的。

A．二叉排序树是动态树表，查找不成功时插入新结点时，会引起树的重新分裂和组合(不用移动元素的树)B．对二叉排序树进行层序遍历可得到有序序列（应该是中序遍历）C．用逐点插入法构造二叉排序树时，若先后插入的关键字有序，二叉排序树的深度最大D．在二叉排序树中进行查找，关键字的比较次数不超过结点数的1/2（取决于二叉排序树的形状）9．一组记录的关键字为{47、75、55、30、42、90}，则用快速排序方法并以第一个记录为支点得到的第一次划分结果是。

数据结构A卷以及答案-考试⽤华东交通⼤学2012—2013学年第⼀学期考试卷试卷编号：（A ）卷数据结构课程课程类别：必考⽣注意事项：1、本试卷共5页，总分100分，考试时间120分钟。

2、考试结束后，考⽣不得将试卷、答题纸和草稿纸带出考场。

⼀、选择题(每题2分，共20分)1、在⼀个链队列中，若f ，r 分别为队⾸、队尾指针，则插⼊s 所指结点的操作为( )(A) f->next=c ；f=s (B) r->next=s ；r=s (C) s->next=r ；r=s (D) s->next=f ；f=s 2、下⾯程序的时间复杂度为（）for(i=0;ifor(j=0;jA[i][j]=i*j;(A) O(M2) (B) O(N2) (C) O(M*N) (D) O(M+N)3、设⾼度为h 的⼆叉树上只有度为0和度为2的结点，则此类⼆叉树中所包含的结点数⾄少为： ( )(A) 2h (B) 2h-1 (C) 2h+1 (D) h+1 4、设指针变量p 指向单链表中结点A ，若删除单链表中结点A ，则需要修改指针的操作序列为（）。

(A) q=p->next ；p->data=q->data ；p->next=q->next ；free(q)； (B) q=p->next ；q->data=p->data ；p->next=q->next ；free(q)； (C) q=p->next ；p->next=q->next ；free(q)； (D) q=p->next ；p->data=q->data ；free(q)；5、含N 个顶点的连通图中的任意⼀条简单路径，其长度不可能超过( )(A) 1(B) N/2 (C) N-1 (D)N6、设⼀组初始关键字记录关键字为(20，15，14，18，21，36，40，10)，则以20为基准记录的⼀趟快速排序结束后的结果为( )。