数据结构试卷B

注意事项：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⽆关的查找⽅法是。

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

一、单项选择题1．算法必须具备的三个特性是( )。

A．可执行性、可移植性、可扩充性B．可执行性、确定性、有穷性C．确定性、有穷性、稳定性D．易读性、稳定性、安全性2．下列数据中，( )是非线性数据结构。

A．栈B．队列C．完全二叉树D．顺序表3．算法分析的两个方面是( )。

A．空间复杂度和时间复杂度B．正确性和简明性C．可读性和文档性D．数据复杂性和程序复杂性4．非空的循环单链表head的尾结点p满足( )。

A．p->next==head B．p->next==NULLC．p==NULL D．p==head5．在单链表指针为p的结点之后插入指针为s的结点，正确的操作是( )。

A．p->next=s;s->next=p->next; B．s->next=p->next;p->next=s;C．p->next=s;p->next=s->next; D．p->next=s->next;p->next=s;6．按照二叉树的定义，具有3个结点的二叉树有( )种。

A．3 B．4C．5 D．67．在一个有向图中，所有顶点的入度之和是所有顶点的出度之和的( )倍。

A．1/2 B．1C．2 D．48．二叉排序树是( )。

A．每一分支结点的度均为2的二叉树B．中序遍历得到一升序序列的二叉树C．按从左到右顺序编号的二叉树D．每一分支结点的值均小于左子树上所有结点的值，大于右子树上所有结点的值9．若用一个大小为6的数组来实现循环队列，且当前rear和front的值分别为0和3，当从队列中删除一个元素，再加入两个元素后，rear和front的值分别是( )。

A．1和 5 B．2和4C．4和2 D．5和110．下列说法中正确的是( )。

A．堆栈是在两端操作、先进后出的线性表B．堆栈是在一端操作、先进先出的线性表C．队列是在一端操作、先进先出的线性表D．队列是在两端操作、先进先出的线性表11．不带头结点的单链表head为空的判定条件是( )。

浙江科技学院考试试卷浙江科技学院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．线性表的顺序存储结构是一种( )的存储结构。

安徽大学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）。

《数据结构》试卷（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进制表示。

数据结构试卷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)个结点的完全二叉树的深度为 。

数据结构试题试卷南京工业大学数据结构试题（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中的叶子数为。

2021-2022-1数据结构期末考试卷B一、单项选择题（共20题，20分）1、采用分块查找时,若线性表共有625个元素,查找每个元素的概率相等,假设采用顺序查找来确定结点所在的块时,每块分( )个结点最佳。

（1.0）A、 6B、 10C、 25D、 625正确答案： C2、计算出的地址分布最均匀的散列函数是( )。

（1.0）A、数字分析法B、除留余数法C、平方取中法D、折叠法正确答案： B3、设S="",则LenStr(S)=( )。

（1.0）A、 0B、 1C、 2D、 3正确答案： A4、设目标串T="aabaababaabaa",模式P="abab",模式匹配算法的外层循环进行了( )次。

（1.0）A、 1B、 4C、 5D、 9正确答案： C5、*下列程序的空间复杂度是( )for (i=1; i<=n; ++i){for (j=1; j<=m; ++j){c [i][j]=0;}}（1.0）A、 O(m*n)B、 O(m+n)C、 O(m-n)D、 O(m/n)正确答案： A6、算法的计算量大小称为算法的( )。

（1.0）A、现实性B、难度C、效率D、时间复杂度正确答案： D7、设数组data[m]作为循环队列SQ的存储空间,front为队头指针,rear为队尾指针,则执行出队操作后其头指针front的值为( )（1.0）A、 front=front+1B、 front=(front+1)%(m-1)C、 front=(front-1)%mD、 front=(front+1)%m正确答案： D8、以下哪一个不是队列的基本运算。

( )（1.0）A、从队尾插入一个新元素B、从队列中删除第i个元素C、判断一个队列是否为空D、读取队头元素正确答案： B9、广义表((a,b),c,d)的表头是( )。

（1.0）A、 aB、 dC、 (a,b)D、 (c,d)正确答案： C10、下列矩阵是一个( )。

第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)条边的连通无向图中，顶点度数最大值为____________。

厦门大学《＿数据结构＿》课程期末试卷信息科学与技术学院计算机科学系2010年级＿＿＿专业主考教师：陈怡疆庄朝晖试卷类型：（B卷）一、（本题10分）回答下列问题，同时举例说明之：（1）在数据结构课程中，数据的逻辑结构，数据的存储结构及数据的运算之间存在着怎样的关系？（2）若逻辑结构相同但存储结构不同，则为不同的数据结构。

这样的说法对吗？（3）在给定的逻辑结构及其存储表示上可以定义不同的运算集合，从而得到不同的数据结构。

这样说法对吗？答：答：（1）数据的逻辑结构反映数据元素之间的逻辑关系（即数据元素之间的关联方式或“邻接关系”），数据的存储结构是数据结构在计算机中的表示，包括数据元素的表示及其关系的表示。

数据的运算是对数据定义的一组操作，运算是定义在逻辑结构上的，和存储结构无关，而运算的实现则是依赖于存储结构。

（2）逻辑结构相同但存储不同，可以是不同的数据结构。

例如，线性表的逻辑结构属于线性结构，采用顺序存储结构为顺序表，而采用链式存储结构称为线性链表。

（3）栈和队列的逻辑结构相同，其存储表示也可相同（顺序存储和链式存储），但由于其运算集合不同而成为不同的数据结构。

二、（本题10分）（1）线性表和树的共同点和不同点是什么？（2）设数组a[0..49,0..79]的基地址为2000，每个元素占2个字节，若以列序为主序顺序存储，则元素a[44,67]的存储地址为多少？答：（1）共同点：线性表和树都是逻辑结构，都可以没有数据元素（空表或空树）。

如果不空，都存在一个无前驱的数据元素，都存在无后继的数据元素。

如果不空，除了无前驱的数据元素外，其余的数据元素均只有一个前驱。

不同点：若不空，线性表只存在一个无后继数据元素（表尾结点），而树可以存在多个无后继数据元素（叶子结点）。

除了无后继数据元素外，在线性表中其它数据元素有一个后继，在树中有多个后继。

（2）2000+(67*50+44)*2=8788三、（本题10分）下面的邻接表表示一个给定的无向图G，（1）画出该无向图G。

试卷编号： （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 ______不可能是它承诺：我将严格遵守考场纪律，知道考试违纪、作弊的严重性，还知道请他人代考或代他人考者将被开除学籍和因作弊受到记过及以上处分将不授予学士学位，愿承担由此引起的一切后果。

安徽大学20 19 —20 20 学年第 1 学期《 数据结构 》考试试卷（B 卷） （闭卷 时间120分钟） 考场登记表序号 一、算法分析题（每小题5分，共25分） 1. 分析下面算法的时间复杂度。

void Fun(int n) { int i,j,m=0; for(i =1; i<=n; i++){ for(j=2*i; j < =n; j ++) m++; } } 2.阅读并分析下面算法，回答问题。

char *Fun(int d) { char e; int i=0, x; static char b[MAXSIZE]; // MAXSIZE 为常量 SqStack st; InitStack(st); while (d != 0) { x = d %16; if (x <10 ) e = '0' + x; else e= 'A' + x -10; Push(st,e); d /= 16; } while (!StackEmpty(st)) { Pop(st, e); b[i++] = e; } b[i] = '\0'; DestroyStack(st); return b; } (1) 请指出Fun(d)算法的功能。

(2) 当d=100时，执行Fun(d)后，数组b 的值是什么？院/系 年级 专业 姓名 学号 答 题 勿 超 装 订 线 ------------------------------装---------------------------------------------订----------------------------------------线---------------------------------------- 题 号 一 二 三 四 五 六 七 总分 得 分 阅卷人 得分3.阅读并分析下面排序算法，回答问题。

《数据结构》模拟试卷（B卷）班级姓名学号一、填空题（每空1分，共10分）1、L是一个带表头结点的单链表，P结点既不是首元结点，也不是尾元结点，在P结点后插入结点Q的语句序列是Q->next=P->next; (1) __ _.2、一个算法的时间复杂度为(3n+nlog2n+n2)，其数量级表示为(2) .3、从稳定性来讲，快速排序是一种(3) 的排序方法。

4、对于一棵二叉树，满足(4) 是满二叉树。

5、后缀算式79 2 30 + - 4 2 / *的值为(5) 。

中缀算式(3+X*Y)-2Y/3对应的后缀算式为(6) 。

6、顺序存储的循环队列队满的判断条件是(7) 。

(Q.rear、Q.front和maxsize分别表示队列的队头指针、队尾指针和队列的存储单元个数)7、*a是平衡二叉树中一个子树的根结点，其平衡因子为1，现在在*a的左子树根结点的左子树上插入一新的结点，使*a的平衡因子变为(8) ，使以*a为根的子树失去平衡，则需进行(9) 的旋转平衡处理。

8、利用给出AOV_网中顶点的拓扑序列的方法可以检查(10) 。

二、单项选择题（每题2分，共20分）1、深度为k的二叉树的结点总数最多为（）。

A．2k-1 B．2k+1 C．2k-1 D．2k-12、假设按低下标优先存储整数数组A6×3×5时，第一个元素的字节地址是100，每个整数占四个字节，则a312的存储地址是( )A.280B.308C.412D.1523、若顺序存储的循环队列的的MaxSize=n,则该队列最多可存储（）个元素。

A.nB.n-1C.n+1D.不确定4、对n个记录进行堆排序，所需要的辅助存储空间为( )A.O(Log2n)B.O(n)C.O(1)D.O(n2)5、下列关于B_树的叙述中，错误的是（）A.一棵m阶的B_树中，每个结点至多有m棵子树；B.一棵m阶的B_树中，每个结点中至多有m个关键字；C.一棵m 阶的B_树中，除根之外的所有非终端结点至少有⎥⎥⎤⎢⎢⎡2m 棵子树； D.一棵m 阶的B_树中，若根结点不是叶子结点则至少有2棵子树6、下列关于AOE 网的叙述中错误的是（ ）A.从源点到汇点的路径长度最长的路径是关键路径；B.完成工程的最短时间是从源点到汇点的最长路径长度；C.提前完成某些关键活动可以加快工程的进度；D.提前完成某些非关键活动可以加快工程的进度7、下列关于二叉树遍历的叙述中，正确的是（ ）A.若一个树叶是某二叉树的中序遍历的最后一个结点，则它必是该二叉树的前序遍历最后一个结点；B.若一个结点是某二叉树的前序遍历的最后一个结点，则它必是该二叉树的中序遍历最后一个结点；C.若一个结点是某二叉树的中序遍历的最后一个结点，则它必是该二叉树的前序遍历最后一个结点；D.若一个树叶是某二叉树的前序遍历的最后一个结点，则它必是该二叉树的中序遍历最后一个结点；8、非空的循环单链表first 的尾结点（由p 所指向）满足（ ）A.p->next=NULLB.p=NULLC.p->next=first C.p=first9、采用邻接表存储的图的深度优先遍历算法类似于树的（ ）A.先序遍历B.中序遍历C.后序遍历D.层序遍历10、对于一个具有n 个顶点和e 条边的无向图，若采用邻接表表示，则所有边链表中边结点的总数为（ ）A.e/2B.eC.2eD.n+e三、应用题（每题10分，共40分）1、试为下列关键字建立一个装填因子不小于0.75的哈希表，并写出你所使用的哈希函数，以及解决冲突的方法，并计算你所构造的哈希表在等概率的情况下查找成功和不成功时的平均查找长度。

数据结构B期末试卷班级学号姓名得分解答题: （共82分）（1） 1.下列程序段或函数的时间复杂度。

（10%）（2） for (int k=0;k<m;k++) （2）int fac(unsigned int n)for (int j=0;j<n;j++) { if (n= =0||n= =1) return 1;a[k][j]=k*j; else return n*fac(n-1);}（3） int Prime(int n) （4）k=1; x=0;{ int k=2 , x=(int)sqrt(n) ; do {while (k<=x) { x++; k*=2;if (n % k= =0) break; }k++; } while (k<n);if (k>x) return 1;else return 0; }2.有A.B.C.D四个元素依次入栈, 即入栈序列唯一, 问共能得到多少种出栈序列？能否得到以下四种出栈序列: ABCD.BDAC.CBDA.DBAC。

对能得到的序列, 请写出Push、Pop序列；对不能得到的序列, 请说明理由。

（6%）3.矩阵Am*n以行优先方式从1000H处开始存放, 元素类型未知, 已知: A[2][3]存放在1011H处, A[1][1]存放在1005H处, 求元素A[2][0]的存放位置。

（6%）4.根据下图所示的树回答问题: （共13%）（1）画出该树等效的二叉树。

（3%）等效的二叉树（2）、写出对该树进行先序、后序遍历的结点序列。

（4%）（3）用带右链的先序表示法来存储此树, 填写下表。

（6%）下标01234567891011siblingelementltag5.假设用于通讯的电文仅由 {ABCDEFGH} 8个字母组成, 字母在电文中出现的频率分别为0.07, 0.19, 0.02, 0.06, 0.32, 0.03, 0.21, 0.10。