数据结构与算法试卷(B卷)

中国矿业大学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）_____最快。

注意事项：1.考生将姓名、学号等信息写在试卷相应位置；2.必须使用蓝(黑)色钢笔或签字笔在规定位置答题；3.注意字迹清楚，保持卷面整洁。

止。

二、填空题(每小题1分，共10分)1. 一个算法具备的5个特性分别是可行性、有穷性、______、输入和输出。

2. 在有n个元素的顺序表中的任意位置插入一个元素所需移动元素的平均次数为______。

3. 栈是一种具有______特性的线性表。

4. 无论是顺序队列还是链式队列，插入和删除运算的时间复杂度都是______。

5. 递归函数f(1)=1，f(n) = f(n-1) + n(n>1)的递归出口是______。

6. 完全二叉树中节点个数为n，则编号最大的分支节点的编号是______。

7. 对n个顶点的连通图来说，它的生成树一定有______边。

8. 采用哈希存储方法时，用于计算节点存储地址的是______。

9. 对二叉排序树进行______遍历，可以得到按关键字从小到大排列的节点顺序。

10．在排序过程中，不比较关键字大小的排序方法是______。

B－2 共13 页.Word 资料三、单向选择题 （每小题2分，共30分）1. 算法的时间复杂度与______有关。

A 、问题规模B 、计算机硬件性能C 、编译程序质量D 、程序设计语言2. 链表不具有的特点是______。

A 、可随机访问任一元素B 、插入删除不需要移动元素C 、不必事先估计存储空间D 、所需空间与线性表长度成正比3. 已知一个栈的进栈顺序是1，2，3，...，n ， 其输出序列是P1, P2,..., Pn, 若P1=n ，则Pi 的值为______。

A 、iB 、n-iC 、n-i+1D 、不确定4. 设顺序循环队列中数组的下标是0～N-1，其头、尾指针分别为f （指向队头元素的前一个位置）和r （指向队尾元素），则其元素个数为______。

A 、r-fB 、r-f-1C 、(r-f)%N+1D 、(r-f+N)%N5. 将递归算法转换成对应的非递归算法时，通常需要使用______保存中间结果。

数据结构试卷B试题B⼀、填空题（18⼩题，40个空，每空分，共20分）1、数据结构是⼀门研究⾮数值计算的程序设计问题中计算机的以及它们之间的和运算等的学科。

2、线性结构中元素之间存在关系，树形结构中元素之间存在关系，图形结构中元素之间存在关系。

3、在顺序表中插⼊或删除⼀个元素，需要平均移动，具体移动的元素个数与有关。

4、在顺序表中访问任意⼀结点的时间复杂度均为，因此，顺序表也称为的数据结构。

5、顺序表中逻辑上相邻的元素的物理位置相邻。

单链表中逻辑上相邻的元素的物理位置相邻。

6、若n为主串长，m为⼦串长，则串的古典（朴素）匹配算法最坏的情况下需要⽐较字符的总次数为。

7、求下列⼴义表操作的结果：（1）GetHead【((a,b),(c,d))】=== ; //头元素不必加括号—（2）GetHead【GetTail【((a,b),(c,d))】】=== ;（3）GetHead【GetTail【GetHead【((a,b),(c,d))】】】=== ;（4）GetTail【GetHead【GetTail【((a,b),(c,d))】】】=== ;8、⼀棵具有２５７个结点的完全⼆叉树，它的深度为。

9、设⼀棵完全⼆叉树具有1000个结点，则此完全⼆叉树有个叶⼦结点，有个度为2的结点，有个结点只有⾮空左⼦树，有个结点只有⾮空右⼦树。

10、图有、等存储结构，遍历图有、等⽅法。

11、n个顶点e条边的图采⽤邻接矩阵存储，⼴度优先遍历算法的时间复杂度为；若采⽤邻接表存储，该算法的时间复杂度为。

12、⽤Dijkstra算法求某⼀顶点到其余各顶点间的最短路径是按路径长度的次序来得到最短路径的。

13、假设在有序线性表a[20]上进⾏折半查找，则⽐较⼀次查找成功的结点数为1；⽐较两次查找成功的结点数为；⽐较四次查找成功的结点数为；平均查找长度为。

14、在各种查找⽅法中，平均查找长度与结点个数n⽆关的查找⽅法是。

⼤多数排序算法都有两个基本的操作：和。

生答题不得过此线··密····························封·························线···························· 院系 专业年级 班级 姓名 学号··················装····························订·························线···························· 一、判断下列命题是否正确（共20分 每题2分）( )1．数据的逻辑结构说明数据元素之间的顺序关系,它依赖于计算机的储存结构。

浙江科技学院考试试卷浙江科技学院2010 -2011 学年第 2 学期考试试卷 B 卷考试科目 数据结构 考试方式 闭 卷 完成时限 120分钟 拟题人 审核人 批准人 年 月 日 理学 院 09 年级 信息与计算科学 专业一、是非题（每小题1分，共10分）正确的在括号内打√，错误的打×.（ ）1. 数据元素是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理.（ ）2. 数据结构是相互之间存在一种或多种关系的数据元素的集合，数据元素相互之间的关系称为结构.（ ）3. 对于抽象数据类型而言，不论其内部结构变化如何，只要它的数学特性不变，都不影响其外部的使用.（ ）4. 线性表的逻辑顺序与物理顺序总是一致的.（ ）5. 每种数据结构都应具备三种基本运算：插入、删除、搜索. （ ）6. 空串与由空格组成的串没有区别. （ ）7. 完全二叉树就是满二叉树.（ ）8. 已知一棵二叉树的前序序列和中序序列，则可以唯一地构造出该二叉树. （ ）9. 带权连通图的最小生成树的权值之和一定小于它的其他生成树的权值之和. （ ）10. 内部排序要求数据一定要以顺序方式存储.二、选择题（单项选择，每小题2分，共40分） 请将你认为正确的选项填入下表中。

专业班级 学号 姓名………………………………………………………………………装订线……………………………………………………………………………………1. 算法在发生非法操作时可以作出处理的特性称为（）.A. 正确性B. 易读性Ｃ.高效率 D. 健壮性2. 执行下面程序段时，执行S语句的次数为（）.for (int i = 1; i <= n; i ++)for (int j = 1; j <= i; j ++) S;A. 2nB. n/2C. n(n+1)D. n(n+1)/23. 数据结构的定义为（D, S），其中S是（）的集合.A. 算法B. 数据元素C. 关系D. 逻辑结构4. 有六个元素按照6,5,4,3,2,1的顺序进栈，则下列（）项不是合法的出栈序列.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. 广义表A（a），则表尾为（）.A. aB. （（））C. 空表D. （a）6. 二叉树中第4层上的结点最多为（）.A. 8B. 15C.16D. 327. 对右图所示二叉树，进行后序遍历的结果是（）.A. ABCDEFB. DBEAFCC. ABDECFD. DEBFCA8. 假设以行序为主序存储二维数组A = array[1..100,1..100]设每个数据元素占两个存储单元，基地址为10，则Loc[5,5]（）.A. 808B. 818C. 1010D. 10209. 具有35个结点的完全二叉树的深度为（）.A. 5B. 6C. 7D. 810. 若一棵二叉树具有9个度为2的结点，则该二叉树的度为0的结点个数是（）.A. 9B. 10C. 11D. 不确定11. 在有n个结点的二叉树的二叉链表表示中，空指针数为（）.A. 不定B. n+1C. nD. n-112. 具有n个结点的二叉树，拥有指向孩子结点的分支数目是（）.A. n-1B. nC. n+1D. 2n13. 在完全二叉树中，若一个结点是叶子结点，则它没有（）.A. 左孩子结点B. 右孩子结点C. 左孩子结点和右孩子结点D. 左孩子结点，右孩子结点和兄弟结点14. 有m个叶子结点的哈夫曼树，其结点总数是（）.A. 2m-1B. 2mC. 2m+1D. 2（m+1）15. 任何一个无向连通图的最小生成树（）.A. 只有一棵B. 有一棵或多棵C. 一定有多棵D. 可能不存在16. 下列查找方法中，（）适合用于查找有序单链表.A. 顺序查找B. 二分查找C. 分块查找D. 哈希查找17. 在长度为100的有序线性表中进行顺序查找，最坏情况下需要比较的次数为（）.A. 99B.100C. 101D. 018. 对关键码序列28，16，32，12，60，2，5，72快速排序，若选28为枢轴记录关键字，则从小到大一次划分结果为（）.A. （2，5，12，16）28（60，32，72）B. （5，16，2，12）28（60，32，72）C. （2，16，12，5）28（60，32，72）D. （5，16，2，12）28（32，60，72）19. 下列排序算法中，（）排序在一趟结束后不一定能选出一个元素放在其最终位置上.A. 选择B. 冒泡C. 归并D. 堆20. 一个序列中有10000个元素，若只想得到其中前10个最小元素，最好采用的排序方法是（）.A. 快速排序B. 堆排序C. 插入排序D. 二路归并排序三、填空题（每空1分，共15分）1. 在线性结构中，____________具有先进先出特性，___________具有先进后出特性.2. 有向图的存储结构有______________、_____________、_____________等方法.3. 具有10个顶点的连通图的深度优先生成树，其边数为_________________.4. 已知U = ’xyxyxyxxyxy’，t = ’xxy’，StrAssign(S, U)，StrAssign(V, Substring(S, Index(s,t), StrLength(t)+1))，StrAssign(m,’ww’)求Replace(S, V, m)=___________________.5. 具有相同函数值的关键字对于哈希函数来说称作__________________.6. 已知一组待排序列的记录关键字初始排序为：56，34，58，26，79，52，64，37，28，84，57.若选中第一个记录关键字为枢轴记录，则一趟快速排序的结果为：_____________________；若建立大根堆，则初始堆为____________________.7. 由A, B, C, D, E五个结点构成的二叉树，共有_________种互不相似的结构.8. 长度为225的表，采用分块查找法，每块的最佳长度是______，应分为______块，若每块的长度为10，则平均查找长度为_________________.9. 快速排序在平均情况下的时间复杂度为_____________.四、应用题(共30分)1. （8分）已知一棵二叉树的中序序列和后序序列如下，求该二叉树的高度（假定空树的高度为-1）和度为2、度为1及度为0的的结点个数.中序序列：CBDEAGIHJF；后序序列：CEDBIJHGFA2. （7分）假设用于通信的电文仅由8种字符母{A，B，C，D，E，F，G，H}组成，它们在电文中出现的频率分别为{0.07，0.19，0.02，0.06，0.32，0.03，0.21，0.10}。

湖北文理学院 2011－2012 学年度下学期《数据结构与算法》试卷B专业：计算机科学与技术姓名： 学号： 班级：一、判断题（本题共10小题，每小题1分，共计10分）。

（正确的打√，错的打×）1、空串和空格串是相同的。

( )2、数据的存储结构是数据及其逻辑结构在计算机中的物理表示。

( )3、大顶堆（最大堆）中，最大值一定为根结点。

( )4、栈是特殊的线性表，它的插入和删除分别在线性表的两端进行。

( )5、稀疏矩阵一般采用三元组顺序表方法压缩存储。

( )6、 若二叉排序树（搜索树）中关键码互不相同，则其中最小元素和最大元素一定是叶子结点。

( )7、有向图用邻接表表示后，顶点i 的出度等于邻接表中顶点i 后链表的长度。

( ) 8、链接线性表是顺序存取的线性表。

( )9、哈希函数进行模除取余时，最好取素数进行模除。

（ ） 10、归并排序是一种稳定的排序算法。

（ ）二、填空题（本题共10小题，每小题 2 分，共计 20分）。

（请将正确答案填入空格内，答案是确定和唯一的）1、在数据结构中，从逻辑上可以把数据结构分成 和 。

2、限在表尾进行插入和删除操作的线性表称为 。

3、实现二分查找（对半搜索）的存储结构仅限于顺序存储结构，且其中元素排列必须是_______的。

4、在拓扑排序中，拓扑序列的第一个顶点必须是 的顶点。

5、在一个长度为n 的顺序表中删除第i 个元素，则需要移动 个元素。

6、二维数组A[6，7]，按列优先存储，每个元素占4个字节,A 基址为500,则元素A[4,6]的存储地址是 。

7、深度为k二叉树中最多可有个结点。

8、任意写出二叉树的两种存储结构，分别是和。

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

10、快速排序平均时间复杂性为，平均空间复杂性。

三、选择题（本题共18小题，每小题 1分，共计 18 分）。

（从下列答案中选出一个正确答案，并将对应的字母填入括号内）1．线性表的顺序存储结构是一种( )的存储结构。

2014-2015学年第2学期考试试题(A)卷课程名称算法与数据结构任课教师签名出题教师签名审题教师签名考试方式(闭)卷适用专业信息与计算机考试时间(120)分钟一、单项选择题（每小题4分，共20分）1、算法的时间复杂度与（）有关。

(A) 问题规模(B) 计算机硬件性能(C) 编译程序质量(D) 程序设计语言2、线性表的链式存储结构与顺序存储结构相比的优点是（）。

(A) 所有的操作算法实现简单(B) 便于随机存取(C) 便于插入和删除操作的实现(D) 便于利用零散的存储器空间3、设10个元素进栈序列是1，2，…，10，其输出序列是a1，a2，…，a10，如果a1=3，则a2的值为（）。

(A) 一定是2 (B) 一定是1(C) 不可能是4 (D) 不可能是14、设高度为h的二叉树上只有度为0和度为2的结点（假设仅含根结点的二叉树的高度为1），则此二叉树所包含的结点数至多有（）。

(A) 2h-1 (B) 2h - 1(C) 2h+1 (D) 2h + 15、设有13个值，用它们组成一棵哈夫曼树，则该哈夫曼树共有（）个结点。

(A) 13 (B) 12(C) 26 (D) 25二、填空题（每小题2分，共10分）1、把一个递归过程转换成一个等价的非递归过程，通常使用（）。

2、数据的逻辑结构是从逻辑上描述数据，它与数据的（）无关，是独立于计算机的。

3、在单链表中，结点与结点之间的逻辑关系不是通过存储单元的顺序来表示的，而是通过（）来实现的。

4、实现动态分配和动态回收一个结点空间的两个标准过程是（）和（）。

三、名词解释（每小题5分，共10分）1、线性表2、哈希函数四、简答题（每小题5分，共10分）1、简述顺序表和链表的优缺点。

2、举例说明直接选择排序方法是一种不稳定的排序方法。

五、应用题（每小题6分，共30分）1、关键字序列{12，7，18，13，17，29，34，6，8}是否为堆？若不是，请将其调整为最小堆，并统计建堆过程中的交换次数。

安徽大学2010—2011学年第2学期《 数据结构 》考试试卷（B 卷） （闭卷 时间120分钟）考场登记表序号一、填空题（每小题1.5分，共15分） 1．含有36个元素的有序表，进行二分查找时的判定树的深度为 6 。

2．在一个无向图中，所有顶点的度数之和等于所有边数的 2 倍。

3． 由带权为9、2、5、7的四个叶子结点构造一棵哈夫曼树，该树的带权路径长度为 44 。

4．由a ，b ，c 三个结点构成的二叉树，共有 5 种不同形态。

5．二维数组A[0‥5][5‥10]以行序为主序存储，每个元素占4个存储单元，且A[0][5]的存储地址是1000，则A[3][9]的地址是 1088 。

6．若串s=''soft ，则其子串个数是 11 。

7. 设循环队列的空间大小为M ，入队时修改队尾指针rear 的语句为 rear=(rear+1)%M 。

8．在顺序存储结构的线性表中，插入或删除一个数据元素大约需移动表中 一半 元素。

9．下列程序段的时间复杂度是 O(m*n) 。

for (i=0;i<n;i++) for (j=0;j<m;j++) A[i][j]+=5;10. 在数据结构中，与所使用的计算机无关的是数据的 逻辑 结构。

二、单项选择题（每小题2分，共20分）1. 数据结构可以用二元组来表示，它包括（ A ）集合D 和定义在D 上的（ C ）集合R 。

A 、数据元素B 、存储结构C 、元素之间的关系D 、逻辑结构2． 已知L 是一个不带头结点的单链表，p 指向其中的一个结点，选择合适的语句实现在院/系 年级 专业 姓名 学号答 题 勿 超 装 订 线 ------------------------------装---------------------------------------------订----------------------------------------线----------------------------------------p结点的后面插入一个结点s的操作（B）。

广州大学学年第学期考试卷课程数据结构与算法考试形式（闭卷，考试）信息学院系专业级班学号：姓名：一、填空题：（每格2分，共20分）1．以{5，6，8，10，15}作为叶子结点的权值所构造的哈夫曼树的带权路径长度是。

2．判断一个无向图是一棵树的条件是。

3．设n0为哈夫曼树的叶子结点数目，则该哈夫曼树共有个结点。

4．一个无序序列可以通过构造一棵树而变成一个有序序列，构造树的过程即为对无序序列进行排序的过程。

5．如果结点A有 3个兄弟，而且B是A的双亲，则B的度是。

6．设有向图有n个顶点和e条边，进行拓扑排序时，总的时间复杂度为7．在排序算法中，每次从未排序的记录中挑出最小（或最大）关键码字的记录，加入到已排序记录的恰当位置，该排序方法叫。

8．用一维数组存放的一棵完全二叉树；ABCDEFGHIJKL。

后序遍历该二叉树的访问结点序列是。

9．设散列函数H(k)=K mod 7,散列表的地址空间为0—6，则关键字为32的元素在哈希表中的下标为。

10．一棵非空二叉树的先序序列和后序序列正好相反，则树的形状是。

二、单项选择题（每题1分，共10分）1．（）设一个栈的输入序列是1，2，3，4，5 则下列序列中，是栈的合法输出序列的是：A. 5 1 2 3 4B. 4 5 1 3 2C. 4 3 1 2 5D. 3 2 1 5 42．（）在图采用邻接表存储时，求最小生成树的prim 算法的时间复杂度为A. O(n)B. O(n+e)C. O(n2)D. O(n3)3．（）下列排序算法中，哪种算法不能保证每趟排序至少能将一个元素放到其最终的位置上？A.快速排序B. shell排序C. 堆排序D. 冒泡排序4.（）一棵非空的二叉排序树在先序线索化后，其中值为空的链域的个数是：A.不确定B. 0C. 1D. 25（）对于线性表最常用的操作是查找指定序号的元素和在末尾插入元素，则选择哪种最节省时间？A．顺序表 B. 单链表C带头接点的双循环链表D带尾接点的单循环链表6（）求解最短路径的Floyd算发的时间复杂度为：A．O(n) B. O(n+c) C. O(n2) D. O(n3)7（）数据序列（8，9，10，4，5，6，20，1，2）只能是下列排序算发中哪种算法的两趟排序后的结果？A．选择排序 B 冒泡排序 C 插入排序 D 堆排序8（）下列序列中，哪个是堆？A．（100，80，55，60，50，40，58，35，20）B．（100，80，55，60，50，40，35，58，20）C．（100，80，55，58，50，40，60，35，20）D．（100，70，55，60，50，40，58，35，20）9（）一棵左子树为空的二叉树在先序线索化后，其中空的链域的个数是：A．不确定 B 0 C 1 D 210（）算术表达式A+B*（C+D/E）转为后缀表达式后为：A：AB+CDE/*B：ABCDE/+*+C：ABCDE/*++D：ABCDE*/++三、判断题（在括号内填上“√”或“╳”，每题1分，共10分，做错不倒扣）1.（）线性表的特点是每个元素都有一个前驱和一个后继。

《数据结构》试卷（B）学号：姓名：日期：一.选择题（每小题2分，共30分，请写在答卷纸上）：1.下面程序的时间复杂为（）。

for（i=1，s=0； i<=n； i++） {t=1；for(j=1；j<=i；j++) t=t*j；s=s+t；}A.O(n)B.O(n2)C.O(n3)D.O(n4)2.设某数据结构的二元组形式表示为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是（）。

A.线性结构B.树型结构C.物理结构D.图状结构3.设指针变量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)；4.栈和队列的共同特点是( )。

A.只允许在端点处插入和删除元素B.都是先进后出C.都是先进先出D.没有共同点5.设某棵二叉树的中序遍历序列为ABCD，先序遍历序列为CABD，则后序遍历该二叉树得到序列为（）。

A.BADCB.BCDAC.CDABD.CBDA6.设有一个二维数组A[m][n]，假设A[0][0]存放位置在644(10)，A[2][2]存放位置在676(10)，每个元素占一个空间，问A[3][3](10)存放在什么位置？脚注(10)表示用10进制表示。

广州大学学年第学期考试卷课程数据结构与算法考试形式（闭卷，考试）信息学院系专业级班学号：姓名：一、填空题：（每格2分，共20分）1．已知二叉树的中序遍历序列为B,H,D,C,E,F,A,G，后遍历序列为H,D,F,E,C,B,G,A,其前序遍历列为。

2．若一个非连通的无向图最多有21条边，则该无向图至少有个顶点。

3．若具有n个顶点的无向连通图采用邻接矩阵表示，则邻接矩阵中至少有________个非零元素。

4．若从无向图的任意一个顶点出发进行一次深度优先搜索便可以访问该图的所有顶点，则该图一定是一个________________图。

5．将数据元素2，4，6，8，10，12，14，16，18，20依次存放于一个一维数组中（设该数组第一个元素的下标为1），然后采用折半查找元素15，被比较过的数组元素的下标依次为_____________。

6．顺序查找法，折半查找法，树形查找法和散列查找法这四种方法中，只有_____________________的平均查找长度与元素的个数n无关。

7．设无向连通图G的顶点数与边数和一立方体相同，即有8个顶点和12条边。

任意一棵G的生成树共有________________条边8．字符串’abcd’中共有________________个长度大于0小于4的子串。

9．将字符数组a[0..7,0..7]按行优先次序存储在起始地址为1000的连续的内存单元中，则元素a[6,2]的地址是：__________________________ 10．已知某带权连通无向图采用邻接矩阵存储方式，邻接矩阵以三元组表形式给出，部包括主对角线元素在内的下三角形部分元素对应的各三元组分别为(2,1,7),(3,1,6),(3,2,8),(4,1,9)(4,2,4),(4,3,6),(5,1,∞),(5,2,4),(5,3,∞),(5,4,2)。

该连通图的最小生成树的权值之和是 。

二、单项选择题（每题1分，共10分）1． （ ）堆排序的时间复杂度和需附加的存储空间分别是： A O(n 2) 和O(1) B O(nlog 2n) 和O(1) C O(nlog 2n)和O(n) D O(n 2)和O(n)2．（ ）最佳二叉排序数的结构特点是：A 除最下两层可以不满外，其余都是满的B 除最下一层可以不满外，其余都是满的C 每个结点的左右子树的高度之差的绝对值不大于1D 最下层的叶子结点必须在最左边3．（ ）设计一个判别表达式中左、右括号是否配对出现的算法，采用什么数据结构最佳？ A 、线性表的顺序存储结构 B 、队列C 、线性表的链式存储结构D 、栈4．（ ）线索二叉树是一种什么结构？ A 逻辑 B 逻辑和存储 C 物理 D 线性 5．（ ）下列排序中，哪个是堆？ A ．（100，80，55，60，50，40，58，35，20）B ．（100，80，55，60，50，40，35，58，20）C ．（100，80，55，58，50，40，60，35，20）D ．（100，70，55，60，50，40，58，35，20）6．（ ）若某完全二叉树的深度为h （设单结点的树的深度为1），则该完全二叉树中至少有几个结点？A ．2hB ．21h -C ．21h +D ．12h -7．（ ）在二叉排序树中进行查找的时间效率与什么有关？A ．二叉排序树的深度B ．二叉排序树的结点的个数C ．被查找结点的度D ．二叉排序树的存储结构8. （ ）若二叉树中度为2的结点有15个，度为1的结点有10个，则该二叉树有几个结点？A．41 B．31 C．25 D．309．（）只能在顺序存储结构上才能实现的查找方法是哪种？A．顺序查找B．树型查找C．折半查找D．散列查找10．（）从未排序序列中任选一个元素，该元素将未排序序列分成前后两个部分，前一部分中所有元素均小于所选元素，而后一部分中所有元素均大于等于所选元素，所选元素处在排序的最终位置，分别对被分成的两部分中元素个数超过1的部分重复上述过程，直至整个排序结束。

数据结构试卷B卷(含答案)-CAL-FENGHAI.-(YICAI)-Company One1《数据结构》试卷B一、填空题（每空1分，共15分）1. 向量、栈和队列都是结构，可以在向量的位置插入和删除元素；对于栈只能在插入和删除元素；对于队列只能在插入和删除元素。

2. 栈是一种特殊的线性表，允许插入和删除运算的一端称为。

不允许插入和删除运算的一端称为。

3. 数据结构是一门研究非数值计算的程序设计问题中计算机的以及它们之间的和运算等的学科。

4. 在顺序表中插入或删除一个元素，需要平均移动元素，具体移动的元素个数与有关。

5. 在具有n个单元的循环队列中，队满时共有个元素。

6. 假设在有序线性表a[20]上进行折半查找，则比较一次查找成功的结点数为1；比较两次查找成功的结点数为；比较四次查找成功的结点数为；平均查找长度为。

二、判断正误（判断下列概念的正确性，并作出简要的说明。

）（每小题1分，共10分）（）1. 线性表的每个结点只能是一个简单类型，而链表的每个结点可以是一个复杂类型。

（）2. 在表结构中最常用的是线性表，栈和队列不太常用。

（）3. 栈是一种对所有插入、删除操作限于在表的一端进行的线性表，是一种后进先出型结构。

（）4. 对于不同的使用者，一个表结构既可以是栈，也可以是队列，也可以是线性表。

（）5.线性表的逻辑顺序与存储顺序总是一致的（）6. 栈和队列是一种非线性数据结构。

（）7. 栈和队列的存储方式既可是顺序方式，也可是链接方式。

（）8. 两个栈共享一片连续内存空间时，为提高内存利用率，减少溢出机会，应把两个栈的栈底分别设在这片内存空间的两端。

（）9. 队是一种插入与删除操作分别在表的两端进行的线性表，是一种先进后出型结构。

（）10. 一个栈的输入序列是12345，则栈的输出序列不可能是12345。

三、单项选择题（每小题1分，共20分）（）1．数据在计算机存储器内表示时，物理地址与逻辑地址相同并且是连续的，称之为：（A）存储结构（B）逻辑结构（C）顺序存储结构（D）链式存储结构（）2. 若已知一个栈的入栈序列是1，2，3，…，n，其输出序列为p1，p2，p3，…，pn，若p1=n，则pi为Ａ．i Ｂ．n=i Ｃ．n-i+1 Ｄ．不确定（）3. 判定一个栈ST（最多元素为m0）为空的条件是Ａ．ST->top<>0 Ｂ．ST->top=0 Ｃ．ST->top<>m0 Ｄ．ST->top=m0（）4设矩阵A是一个对称矩阵，为了节省存储，将其下三角部分（如下图所示）按行序存放在一维数组B[ 1, n(n-1)/2 ]中，对下三角部分中任一元素a i,j(i≤j), 在一维数组B中下标k的值是：Ａ．i(i-1)/2+j-1 Ｂ．i(i-1)/2+j Ｃ．i(i+1)/2+j-1 Ｄ．i(i+1)/2+j（ ）5．具有n(n>0)个结点的完全二叉树的深度为 。

广州大学学年第学期考试卷课程数据结构与算法考试形式（闭卷，考试）信息学院系专业级班学号：姓名：一、填空题：（每格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．后序线索二叉树中求后序后继。

数据结构试题试卷南京工业大学数据结构试题（b）卷（闭）2021--2021学年第二学期使用班级地信0401-02班级学号姓名题号罚球一二三四五总分一、选择题（15×2’＝30’）1.算法的计算量的大小称为计算的。

a．效率b．复杂性c．现实性d．难度2.从逻辑上可以把数据结构分成两大类。

a．动态结构、静态结构b．顺序结构、链式结构c．线性结构、非线性结构d．初等结构、构造型结构3.以下数据结构中，是非线性数据结构。

a．树b．线性表c．队d．栈4.下面观点错误的就是。

(1)算法原地工作的含义是指不需要任何额外的辅助空间(2)在相同的规模n之下，复杂度o(n)的算法在时间上总是强于复杂度o(2n)的算法(3)所谓时间复杂度就是指最坏情况下，估计算法继续执行时间的一个上界(4)同一个算法，同时实现语言的级别越高，继续执行效率就越高a．（1）b．（1）（2）c．（3）d．（1）（4）5.下述哪一条是顺序存储结构的优点？a．存储密度大b．插入运算方便c．删除运算方便d．可方便地用于各种逻辑结构的存储表示6.设一个链表最常用的操作方式就是在末尾填入结点和删掉尾结点，则采用最节省时间。

a．单链表中b．单循环链表c．拎尾指针的单循环链表d．率先垂范结点的双循环链表7.若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法的时间复杂德博瓦桑县(1<=i<=n+1)。

a．o(0)b．o(1)c．o(n)d．o(n2)南京工业大学第1页共3页8.下面关于串的的描述中，哪一个就是不恰当的？。

a．串成就是字符的非常有限序列b．空串就是由空格形成的串c．模式匹配就是串成的一种关键运算d．串成既可以使用顺序存储，也可以使用链式存储9.设有数组a[i,j]，数组的每个元素长度为3字节，i的值为1到8，j的值为1到10，数胡海宾内存首地址ba已经开始顺序放置，当用来列入主放置时，元素a[5，8]的存储首地址为a．ba+141b．ba+180c．ba+222d．ba+22510.设树t的度为4，其中度为1，2，3和4的结点个数分别为4，2，1，1则t中的叶子数为。

装订线合肥学院2009至2010学年第2学期算法与数据结构课程考试(B )卷数学与物理系08级信息与计算科学专业学号姓名一、单选题(共20分。

每小题2分。

)01、算法分析的主要任务是分析__ __。

A)算法是否具有较好的可读性B)算法中是否存在语法错误C)算法的功能是否符合设计要求D)算法的执行时间和问题规模之间的关系02、在一个带头结点的双向循环链表中，若要在指针p所指向的结点之后插入一个q指针所指向的结点，则需要对q->next赋值为__ __。

A)p->priorB)p->nextC)p->next->next D)p->prior->prior03、判定栈S(元素个数最多n个)满的条件是__ __。

A)S->top==0 B)S->top!=0C)S->top!=n-1 D)S->top==n-104、设矩阵A是一个对称矩阵(下标从1开始)，为了节省存储，将其下三角部分按行序存放在一维数组B[1,n(n-1)/2]中，则下三角部分中任一元素ai,j(i≤j), 在一维数组B 中下标k的值是_ _。

A) i*(i-1)/2+j-1 B)i*(i-1)/2+jC) i*(i+1)/2+j-1 D)i*(i+1)/2+j05、如果二叉树中结点的前序序列是...a...b...，中序序列是...b...a...，则__ __。

A)结点a和结点b分别在某结点的左子树和右子树中B)结点b在结点a的右子树中C)结点b在结点a的左子树中D)结点a和结点b分别在某结点的两棵非空子树中06、有n个叶子的哈夫曼树的结点总数为_ _。

A)不确定 B)2n C)2n+1 D)2n-107、下图若从顶点a出发按深度优先搜索法进行遍历，则得到的顶点序列是__ __。

A)abecd B)acebd C)aebcd D)aedcb08、带权有向图G用邻接矩阵A存储，则顶点i的入度等于A中。

第2页共4页19． n 条边的无向图的邻接表的存储中，边结点的个数有（） A .n B .2n C .n/2 D. n*n 20．顺序查找适合于存储结构为（）的线性表 A. 哈希存储 B.压缩存储 C.顺序存储或链表存储 D.索引存储二．判断题(本大题共10小题，每小题1分，共10分)请在每小题的括号中填上正确答案。

错填、不填均无分。

1. 在线性表的链式存储结构中，逻辑上相邻的元素在物理位置上不一定相邻。

( )2. 若采用三元组压缩技术存储稀疏矩阵，只要把每个元素的行下标和列下标互换，就完成了对该矩阵的转置运算( )3. 插入排序是稳定的，希尔排序是不稳定的。

( )4. .二叉树中的叶子结点就是二叉树中没有左右子树的结点。

( )5. 有向图的邻接表和逆邻接表中的结点数一定相同。

( )6. 用相邻矩阵表示图所用的存储空间大小与图的边数成正比。

（）7. 霍夫曼树一定是满二叉树。

（）8. 栈是一种线性结构。

（）9. 求最小生成树的Prim 算法在边较少，节点较多时效率高。

（）10. 对二叉排序树进行中序遍历得到的序列是由小到大有序的。

( ) 三、填空题(本大题共10小题，每小题2分，共20分)请在每小题的空格中填上正确答案。

错填、不填均无分。

1． 在一个单链表中p 所指结点之后插入一个由指针f 所指结点，应执行s->next=________;和p->next=s 的操作。

2． 在一个长度为n 的循环链表中，删除其元素值为x 的结点的时间复杂度为_____。

3． 假设以行优先顺序存储三维数组A[5][6][7]，其中元素A[0][0][0]的地址为1100，且每个元素占2个存储单元，则A[4][3][2]的地址是________。

4． 深度为k(k>0)的二叉树最多有___________个结点。

5． 串中所含字符个数称为该串的_____ ______。

6． n(n>0)个结点、(n-1)条边的连通无向图中，顶点度数最大值为____________。

试卷编号： （B ）卷数据结构 课程 课程类别：必 开卷(范围)（ A4纸一张 ）：考生注意事项：1、本试卷共 页，总分 分，考试时间 分钟。

2一、 选择题(每题 2 分，共30分)1. 假设某算法语句总的执行次数为T(n)=5n 5+n³+n²,那么该算法的时间复杂性量级为__B _____。

A) O(2) B) O(n 5) C) O(n 4) D) O(1)2. 若长度为n 的线性表采用顺序存储结构，删除它的第i 数据元素，需要先依次向前移动___A____个数据元素。

( )A) n-i B) n+i C) n-i-1 D) n-i+13. 在一个采用顺序存储方式的线性表中，若表的第一个元素的存储地址是100，每一个元素的长度为2，则第5个元素的地址是 B A) 110 B) 108 C) 100 D) 1204. 从逻辑结构上可以把数据结构分为 C 两大类。

A ．动态结构、静态结构B ．顺序结构、链式结构C ．线性结构、非线性结构D ．初等结构、构造型结构 5. 对线性表，在下列哪种情况下应当采用链表表示？ BA ）经常需要随机地存取元素B ）经常需要进行插入和删除操作C ）表中元素需要占据一片连续的存储空间D ）表中元素的个数不变 6. 带头结点的单链表为空的判断条件是 B 。

A) head==NULL B) head->next==NULL C) head->next==head D) head!=NULL 7. 以下哪一个术语与数据的具体存储结构无关？ A A)栈 B)三元组表 C)线索二叉树 D)双向链表 8. 栈的插入和删除操作在（ A ）进行。

A 栈顶B 栈底C 任意位置D 指定位置9. 某堆栈的输入序列为a,b,c,d,下面的四个序列中，____C ______不可能是它承诺：我将严格遵守考场纪律，知道考试违纪、作弊的严重性，还知道请他人代考或代他人考者将被开除学籍和因作弊受到记过及以上处分将不授予学士学位，愿承担由此引起的一切后果。