北邮数据结构期末考试试题

数据结构期末考试题及答案一、单项选择题（每题2分，共20分）1. 在数据结构中，算法的时间复杂度是指（）。

A. 执行算法所需要的计算工作量B. 执行算法所需要的存储空间C. 执行算法所需要的时间D. 执行算法所需要的内存大小答案：A2. 线性表的顺序存储结构和链式存储结构相比，其优点是（）。

A. 插入和删除操作快B. 存储密度高C. 存储空间可以动态分配D. 存储空间利用率高答案：B3. 栈的基本运算中，不包括（）。

A. 入栈B. 出栈C. 取栈顶元素D. 排序答案：D4. 在二叉树的遍历中，先序遍历的顺序是（）。

A. 先根后子B. 先子后根C. 先左后右D. 先右后左答案：A5. 哈希表解决冲突的方法不包括（）。

A. 分离链接法B. 线性探测法C. 链地址法D. 二分查找法答案：D6. 一个图的邻接矩阵表示法中，若第i行第j列的元素为1，则表示（）。

A. 顶点i和顶点j之间有一条边B. 顶点i和顶点j之间没有边C. 顶点i和顶点j之间有n条边D. 顶点i和顶点j之间有m条边答案：A7. 在查找算法中，二分查找法适用于（）。

A. 线性表B. 哈希表C. 树形结构D. 图结构答案：A8. 快速排序算法的时间复杂度在最坏情况下是（）。

A. O(n)B. O(nlogn)C. O(n^2)D. O(2^n)答案：C9. 一个有n个顶点的无向图，其边数最多为（）。

A. nB. n(n-1)/2C. n(n+1)/2D. 2n答案：B10. 以下哪个不是排序算法（）。

A. 冒泡排序B. 选择排序C. 插入排序D. 归并排序答案：D二、填空题（每题2分，共20分）1. 在数据结构中，一个算法的空间复杂度是指算法执行过程中所需要的___________。

答案：存储空间2. 线性表的链式存储结构中，每个节点包含___________和___________。

答案：数据元素，指针3. 栈的特点是___________，___________。

一、单选题1、逻辑上通常可以将数据结构分为( )A.初等结构和组合结构B.顺序结构和链式结构C.线性结构和非线性结构D.动态结构和静态结构正确答案：C2、如果在数据结构中每个数据元素只可能有一个直接前驱，但可以有多个直接后继，则该结构是()。

A.栈B. 队列C.图D.树正确答案：D3、在长度为n的顺序表的第i个位置上插入一个元素(1<=i<=n+1)，元素的移动次数为：（）A.n-iB.i-1C.n-i+1D.i正确答案：C4、在非空线性链表中由p所指结点的后面插入一个由q所指的结点，应依次执行（）A.q->next=p；p->next=q；B.p->next=q；q->next=p；C.q->next=p->next；p->next=q；D.q->next=p->next；p=q；正确答案：C5、已知栈的最大容量为4。

若进栈序列为1，2，3，4，5，6，且进栈和出栈可以穿插进行,则可能出现的出栈序列为（）A.2，3，5，6，1，4B.1，4，6，5，2，3C.5，4，3，2，1，6D.3，2，5，4，1，6正确答案：D6、设栈S和队列Q初始均为空，若6个元素入栈的顺序为1、2、3、4、5、6，一个元素出栈以后立即入队列Q，若6个元素出队的顺序为2、4、3、6、5、1，则栈S的容量至少为（）A.3B.5C.4D.2正确答案：A7、在计算机内实现递归算法时所需的辅助数据结构是（）A.队列B.栈C.图D.树正确答案：B8、循环队列存储在数组A[0..m-1],则出队时的操作为（）A.front=(front mod m)+1B.ront=(front+1)mod mC.front=front+1D.front=(front+1)mod (m-1)正确答案：B9、若以S和X分别表示进栈和退栈操作，则对初始状态为空的栈可以进行的栈操作系列合法的是（)A.SXXSXSSXB.SSSXXSXXC.SXSSXXXXD.SXSXXSSX正确答案：B10、在具有m个单元的循环队列中，队头指针为front，队尾指针为rear，则队满的条件是（）A.(front+1)%m==rearB.(rear+1)%m==frontC.front==rearD.rear+1==front正确答案：B11、在表长为n的顺序表上做插入运算，平均要移动的结点数为（）A.n/4B.nC.n/3D.n/2正确答案：D12、元素的进栈次序为A，B，C，D，E，则退栈中不可能的序列是（）A.E，D，C，B，AB.A，B，C，D，EC.E，A，B，C，DD.B，C，D，E，A正确答案：C13、下述二叉树中，（）满足性质：从任一结点出发到根的路径上所经过的结点序列按其关键字有序。

数据结构期末考试试题及答案一、选择题1. 评价一个算法时间性能的主要标准是( )。

A、算法易于调试B、算法易于理解C、算法的稳定性和正确性D、算法的时间复杂度2. 计算机算法具备有输入、输出、（）等五个特性。

A、可行性、可移植性和可扩充性B、可行性、确定性和有穷性C、确定性、有穷性和稳定性D、易读性、稳定性和安全性3. 带头结点的单链表head为空的判定条件是（）。

A、head==NULLB、head->next==NULLC、head->next==headD、head！=NULL4. 以下关于线性表的说法不正确的是( )。

A、线性表中的数据元素可以是数字、字符、记录等不同类型。

B、线性表中包含的数据元素个数不是任意的。

C、线性表中的每个结点都有且只有一个直接前趋和直接后继。

D、存在这样的线性表：表中各结点都没有直接前趋和直接后继。

5. 在顺序表中，只要知道( )，就可在相同时间内求出任一结点的存储地址。

A、基地址B、结点大小C、向量大小D、基地址和结点大小6. ( )运算中，使用顺序表比链表好。

A、插入B、删除C、根据序号查找D、根据元素值查找7. 一个长度为n的顺序表中，向第i个元素之前插入一个新元素时，需要向后移动（）个元素A、n-iB、n-i+1C、n-i-1D、i8. ( )适合作为经常在首尾两端操作线性表的存储结构。

A、顺序表B、单链表C、循环链表D、双向链表9. 栈和队列的共同点是（）A、都是先进后出B、都是先进先出C、只允许在端点处插入和删除元素D、没有共同点10. 一个队列的入列序列是1 2 3 4，则队列的输出序列是( )。

A、4 3 2 1B、1 2 3 4C、1 4 3 2D、3 2 4 111. 队列与一般的线性表的区别在于( )。

A、数据元素的类型不同B、运算是否受限制C、数据元素的个数不同D、逻辑结构不同12. “假上溢”现象会出现在( )中。

A、循环队列B、队列C、链队列D、顺序队列二、填空题1．数据的逻辑结构被分为集合、线性结构、树形结构和图结构。

数据结构期末考试试题(含答案)C.{100,98,85,77,80,60,82,40,20,10,66} 答：C。

10.在哈夫曼编码中，若有n个字符，其权值分别为w1，w2，…，wn，编码长度分别为l1，l2，…，ln，则哈夫曼编码的平均长度为a。

A.∑(wi/2li)B.∑(wi/li)C.∑(wi/2li-1)D.∑(wi/li-1)答：A。

2005-2006学年第二学期“数据结构”考试试题（A）要求：所有的题目的解答均写在答题纸上。

每张答题纸上需写清楚姓名、班号和学号，并在上面写上题目的序号。

一、单项选择题（每小题2分，共20分）1.数据的运算效率与采用何种存储结构有关。

因此，选项A是正确答案。

2.链表不具备的特点是可随机访问任一结点。

参见本节要点3.因此，选项A是正确答案。

3.在顺序表中删除一个元素的时间复杂度为O(n)。

因此，选项C是正确答案。

4.具有随机存取功能的线性表存储结构是顺序表。

因此，选项D是正确答案。

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

因此，选项C是正确答案。

6.循环队列qu的队空条件是qu.rear==qu.front。

因此，选项D是正确答案。

7.两个串相等必有串长度相等且串中各位置字符均对应相等。

因此，选项B是正确答案。

8.用直接插入排序对下面四个序列进行递增排序，元素比较次数最少的是21,32,46,40,80,69,90,94.因此，选项C是正确答案。

9.以下序列不是堆（大根或小根）的是{100,98,85,77,80,60,82,40,20,10,66}。

因此，选项C是正确答案。

10.在哈夫曼编码中，若有n个字符，其权值分别为w1，w2，…，wn，编码长度分别为l1，l2，…，ln，则哈夫曼编码的平均长度为∑(wi/2li)。

因此，选项A是正确答案。

C。

{10.20.40.60.66.77.80.82.85.98.100}D。

2022年北京邮电大学计算机科学与技术专业《数据结构与算法》科目期末试卷A（有答案）一、选择题1、无向图G=(V，E)，其中：V={a，b，c，d，e，f}，E={(a，b)，(a， e)，(a，c)，(b，e)，(c，f)，(f，d)，(e，d)}，对该图进行深度优先遍历，得到的顶点序列正确的是（）。

A.a，b，e，c，d，fB.a，c，f,e，b，dC.a，e，b，c，f, dD.a，e，d，f，c，b2、设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主存储， a11为第一元素，其存储地址为1，每个元素占一个地址空间，则a85的地址为（）。

A.13B.33C.18D.403、某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（）存储方式最节省运算时间。

A.单链表B.仅有头指针的单循环链表C.双链表D.仅有尾指针的单循环链表4、最大容量为n的循环队列，队尾指针是rear，队头：front，则队空的条件是（）。

A.（rear+1）MOD n=frontB.rear=frontC.rear+1=frontD.（rear-1）MOD n=front5、下列关于AOE网的叙述中，不正确的是（）。

A.关键活动不按期完成就会影响整个工程的完成时间B.任何一个关键活动提前完成，那么整个工程将会提前完成C.所有的关键活动提前完成，那么整个工程将会提前完成D.某些关键活动若提前完成，那么整个工程将会提前完成6、下列关于无向连通图特性的叙述中，正确的是（）。

Ⅰ．所有的顶点的度之和为偶数Ⅱ．边数大于顶点个数减1 Ⅲ．至少有一个顶点的度为1A．只有Ⅰ B．只有Ⅱ C．Ⅰ和Ⅱ D．Ⅰ和Ⅲ7、若一棵二叉树的前序遍历序列为a，e，b，d，c，后序遍历序列为b， c，d，e，a，则根结点的孩子结点（）。

A．只有e B．有e、b C．有e、c D．无法确定8、一棵哈夫曼树共有215个结点，对其进行哈夫曼编码，共能得到（）个不同的码字。

2022年北京邮电大学网络工程专业《计算机系统结构》科目期末试卷A（有答案）一、选择题1、"从中间开始"设计的"中间"目前多数是在( )。

A.传统机器语言级与操作系统机器级之间B.传统机器语言级与微程序机器级之间C.微程序机器级与汇编语言机器级之间D.操作系统机器级与汇编语言机器级之间2、全相联地址映象是指（）。

A.任何虚页都可装入主存中任何实页的位置B.一个虚页只装进固定的主存实页位置C.组之间是固定的，而组内任何虚页可以装入任何实页位置D.组间可任意装入，组内是固定装入3、与流水线最大吞吐率高低有关的是( )A.各个子过程的时间B.最快子过程的时间C.最慢子过程的时间D.最后子过程的时间4、浮点数尾数基值rm=8，尾数数值部分长6位，可表示的规格化最小正尾数为( )A.0.5B.0.25C.0.125D.1/645、对汇编语言程序员透明的是（）A.I/O方式中的DMA访问B.浮点数据表示C.访问方式保护D.程序性中断6、外部设备打印机适合于连接到( )。

A.数组多路通道B.字节多路通道C.选择通道D.任意一种通道7、对系统程序员不透明的应当是( )。

A.Cache存贮器XB.系列机各档不同的数据通路宽度C.指令缓冲寄存器D.虚拟存贮器8、下列说法正确的是( )A.Cache容量一般不大，命中率不会很高B.Cache芯片速度一般比CPU的速度慢数十倍C.Cache本身速度很快。

但地址变换的速度很慢D.Cache存贮器查映象表和访问物理Cache其间可以流水，使速度与CPU匹配9、在多用户机器上，应用程序员不能使用的指令是（）A.“执行”指令B.“访管”指令C.“启动IO”指令D“测试与置定”指令10、“启动I/O”指令是主要的输入输出指令，是属于（）。

A.目态指令B.管态指令C.目态、管态都能用的指令D.编译程序只能用的指令二、判断题11、软硬功能分配时，提高软件功能的比例会提高系统灵活性，也会提高解题速度。

《数据结构》试题（A卷）（考试时间：90分钟）一、单项选择题（本大题共15小题，每小题2分，共30分）（每题只有一个选项是正确的,将答案填写在括号内，错选、多选不得分）1.（）是组成数据的基本单位，是一个数据整体中相对独立的单元。

A．数据 B.数据元素 C.数据对象 D.数据结构2.算法计算量的大小称为算法的（）。

据的存3.4.5.6.7.8.A.线性表采用顺序存储，必须占用一片连续的存储单元。

B.线性表采用顺序存储，便于进行插入和删除操作。

C.线性表采用链式存储，不必占用一片连续的存储单元。

D.线性表采用链式存储，便于插入和删除操作。

9.队列操作的原则是（）。

A.后进先出B.先进先出C.只能进行插入D.只能进行删除10.栈中允许进行插入和删除的一端称为（）。

A.栈首B.栈尾C.栈顶D.栈底11．假设以数组A[n]存放循环队列的元素，其首尾指针分别为front和rear，则当前队列中的元素个数为（）。

A．（rear-front+n）%nB.rear-front+1C.(front-rear+n)%nD.(rear-front)%n12.最大容量为n的循环队列，队尾指针是rear，队首指针是front，则队空的判断条件是（）。

13.构。

14.15.12在q3．放了2个字符。

4．广义表（a,b,c,d）的表尾是。

5．一棵深度为k的二叉树，最多有个结点。

6．已知有向图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的拓扑序列是______。

7.有n个顶点的连通图至少有条边。

8.1.（）23.4（）5.6.7.8.9.（）10.采用线性探测法解决冲突问题，所产生的一系列后继散列地址必须大于等于原散列址。

数据结构期末考试试题(含答案)题目一请写出快速排序算法的递归实现。

解答一public class QuickSort {public void sort(int[] arr, int low, int high) {if (low < high) {int partitionIndex = partition(arr, low, high);sort(arr, low, partitionIndex - 1);sort(arr, partitionIndex + 1, high);}}private int partition(int[] arr, int low, int high) {int pivot = arr[high];int i = low - 1;for (int j = low; j < high; j++) {if (arr[j] <= pivot) {i++;swap(arr, i, j);}}swap(arr, i + 1, high);return i + 1;}private void swap(int[] arr, int i, int j) {int temp = arr[i];arr[i] = arr[j];arr[j] = temp;}}题目二请解释什么是二叉搜索树，并给出一个例子。

解答二二叉搜索树是一种有序的二叉树，其中每个节点的值大于其左子树的所有节点的值，小于其右子树的所有节点的值。

下面是一个二叉搜索树的例子：6/ \3 9/ \ \1 4 12题目三请写出深度优先搜索(DFS)算法的递归实现。

解答三import java.util.*;public class DFS {private int numVertices;private List<List<Integer>> adjList;public DFS(int numVertices) {this.numVertices = numVertices;adjList = new ArrayList<>();for (int i = 0; i < numVertices; i++) {adjList.add(new ArrayList<>());}}public void addEdge(int src, int dest) { adjList.get(src).add(dest);}public void DFSUtil(int start, boolean[] visited) { visited[start] = true;System.out.print(start + " ");List<Integer> neighbors = adjList.get(start);for (int neighbor : neighbors) {if (!visited[neighbor]) {DFSUtil(neighbor, visited);}}}public void DFS(int start) {boolean[] visited = new boolean[numVertices];DFSUtil(start, visited);}}以上是数据结构期末考试试题及其答案。

数据结构期末考试试卷及答案一、选择题（每题2分，共20分）1. 下列哪一个不是线性结构的特点？A. 有且只有一个根结点B. 每个结点最多有一个前驱和一个后继C. 有多个根结点D. 有且只有一个叶子结点答案：C2. 在单链表中，头结点的作用是（）A. 作为链表的起点B. 作为链表的终点C. 存储链表中的数据元素D. 作为链表中的第一个元素答案：A3. 在顺序表中，插入一个元素的时间复杂度是（）A. O(1)B. O(n)C. O(logn)D. O(n^2)答案：B4. 下列哪种排序算法的平均时间复杂度最高？A. 冒泡排序B. 快速排序C. 直接插入排序D. 希尔排序答案：C5. 在二叉树中，具有3个结点的二叉树有（）种不同的形态。

A. 2B. 3C. 4D. 5答案：C6. 下列哪种情况不适合使用哈希表？A. 查找速度快B. 数据量较大C. 数据量较小D. 数据元素关键字分布均匀答案：C7. 在图的遍历过程中，下列哪种遍历方法属于深度优先遍历？A. 广度优先遍历B. 深度优先遍历C. 混合遍历D. 随机遍历答案：B8. 下列哪种数据结构不适用于实现栈？A. 顺序表B. 链表C. 树D. 图答案：C9. 在双向链表中，删除一个元素的时间复杂度是（）A. O(1)B. O(n)C. O(logn)D. O(n^2)答案：A10. 下列哪种情况不适合使用队列？A. 数据元素先进先出B. 数据元素后进先出C. 数据元素随机进出D. 数据元素按顺序进出答案：B二、填空题（每题2分，共20分）1. 线性表是具有______个数据元素的有限序列。

答案：n2. 在单链表中，每个结点包含两个域：数据域和______域。

答案：指针3. 在顺序表中，插入一个元素的时间复杂度是______。

答案：O(n)4. 快速排序的平均时间复杂度为______。

答案：O(nlogn)5. 哈希表中的冲突指的是______。

答案：不同的关键字对应同一存储位置6. 在图的遍历过程中，深度优先遍历算法使用的数据结构是______。

北京邮电大学2009-2010学年第1学期《数据结构》期末考试试题B卷一、填空题（每空2分，共20分）1、数据元素之间的关系在计算机中有顺序映射像和非顺序映射两种表示方法，由此得到顺序存储结构和______________结构两种不同的存储结构。

2、假设某算法中基本操作的执行额度3n+nlogn,则算法的时间复杂度为___________。

3、在无表头节点的单链表L的表头处插入S结点所应进行的操作是____________________。

4、设循环队列的容量为50，且队头指针和队尾指针分别为front和rear,若front=28,rear=10,则队列中现有________个元素。

5、已知二叉树中叶子结点的数目为50，仅有一个孩子的结点为20，则总结点数为________。

6、用冒泡排序法对a个数据进行排序，第一趟比较_________次。

7、已知下列字符串：a=’THIS’;f=’A SAMPLE’;c=’’(空格);s=Concat(a,Concat(SubString(f,2,7),Concat(c,SubString(a,3,2))));此时，StrLength(s)为_____________。

8、N+1个顶点的连通图至少有____________条边。

9、无向图中各顶点的度数之和为80，那么该图的边数为___________。

10、一棵深度为5的二叉树，最少有_____________结点。

二、判断题，在括号中画×或√（每小题1分，共10分）1、排序是队列的基本操作。

（）2、二叉平衡树的中序遍历值是非递减的。

（）3、线性表的逻辑顺序与存储顺序总是一致的（）4、消除递归必须使用栈。

（）5、串是一种特殊的线性表，其特殊性体现在数据元素可以是若干个字符。

（）6、一般在哈夫曼树中，权值越大的叶子离根节点越近。

（）7、已知二叉树的前序和后序遍历序列能唯一地确定这棵树。

（）8、用邻接矩阵法存储一个图时，所占用的存储空间大小不仅与图中结点个数有关，而且与图的边数有关。

数据结构期末考试真题及答案期末样卷参考答案一．是非题〔每题1分共10分〕1. 线性表的链式存储结构优于顺序存储结构。

F2. 栈和队列也是线性表。

如果需要，可对它们中的任一元素进行操作。

F3．字符串是数据对象特定的线性表。

T4．在单链表P指针所指结点之后插入S结点的操作是：P->next= S ; S-> next = P->next; F5．一个无向图的连通重量是其极大的连通子图。

T 6．邻接表可以表示有向图，也可以表示无向图。

T 7．假设B是一棵树，B′是对应的二叉树。

则B的后根遍历相当于B′的中序遍历。

T8．通常，二叉树的第i层上有2i-1个结点。

F9．对于一棵m阶的B-树,树中每个结点至多有m 个关键字。

除根之外的全部非终端结点至少有ém/2ù个关键字。

F10．对于任何待排序序列来说，快速排序均快于起泡排序。

F二．选择题〔每题2分共28分〕1．在以下排序方法中，〔c 〕方法平均时间复杂度为0(nlogn)，最坏情况下时间复杂度为0(n2)；〔d 〕方法全部情况下时间复杂度均为0(nlogn)。

a. 插入排序b. 希尔排序c. 快速排序d. 堆排序2. 在有n个结点的二叉树的二叉链表表示中，空指针数为〔 b 〕。

a.不定b.n+1c.nd.n-13. 以下二叉树中，〔a 〕可用于完成符号不等长高效编码。

a.最优二叉树b.次优查找树c.二叉平衡树d.二叉排序树4. 以下查找方法中，〔a 〕适用于查找有序单链表。

a.顺序查找b.二分查找c.分块查找d.哈希查找5. 在顺序表查找中，为防止查找过程中每一步都检测整个表是否查找完毕，可采纳〔 a 〕方法。

a.设置监视哨b.链表存贮c.二分查找d.快速查找6. 在以下数据结构中，〔c 〕具有先进先出特性，〔b 〕具有先进后出特性。

a．线性表b．栈c．队列d．广义表7．具有m个结点的二叉排序树，其最大深度为〔f 〕，最小深度为〔 b 〕。

一、单项选择题（10 小题，每小题 1 分，共 10 分）1． 在解决计算机主机与打印机之间速度不匹配问题时通常设置一个打印缓冲区，该缓冲区应该是一个（B ）结构。

B ．队列A ．栈C ．数组D ．线性表）。

D ．123． 设输入序列为 1、2、3、4、5、6，则通过栈的作用后可以得到的输出序列为(2． 设某棵二叉树中有 2000 个结点，则该二叉树的最小高度为（A ．9B ．10C ．11CB)。

A ．5，3，4，6，1，2C ．3，1，2，5，4，6B ．3，2，5，6，4，1D ．1，5，4，6，2，34． 设指针变量 p 指向单链表中结点 A ，若删除单链表中结点 A ，则需要修改指针的操作序列为()。

AA. 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 个关键字序列{k ，k ，…，k }，当且仅当满足关系 k ≤k 且 k ≤k 2 i+1（2i ≤n, 2i+1≤n ）12n i 2i i 称其为小根堆，反之，当且仅当满足关系 k ≥k 且 k ≥k 2i+1（2i≤n, 2i+1≤n ）则为大根堆，以下i 2i i 序列中(C)不符合堆的定义。

A ．（4,10,15,72,39,23,18）C ．（4,10,18,72,39,23,15）B ．（58,27,36,12,8,23,9）D ．（58,36,27,12,8,23,9）6． 程序段for(i=n-1;i>=1;i--)for(j=1;j<=i;j++)if(A[j]>A[j+1])A[j]与 A[j+1]对换；其中 n 为正整数，则最后一行的语句频度在最坏情况下是( B )。

“数据结构”期末考试试题一、单选题(每小题2分,共12分）1．在一个单链表HL中，若要向表头插入一个由指针p指向的结点,则执行（ )。

A． HL＝ps p一>next＝HLB． p一>next＝HL；HL＝p3C． p一>next＝Hl；p＝HL；D． p一〉next＝HL一>next;HL一〉next＝p；2．n个顶点的强连通图中至少含有（ ).A。

n—l条有向边 B.n条有向边C.n(n—1)／2条有向边 D。

n（n一1）条有向边3。

从一棵二叉搜索树中查找一个元素时,其时间复杂度大致为（ )。

A。

O(1) B。

O（n）C.O(1Ogzn）D.O(n2）4．由权值分别为3，8，6，2，5的叶子结点生成一棵哈夫曼树，它的带权路径长度为（）。

A．24 B．48C． 72 D． 535．当一个作为实际传递的对象占用的存储空间较大并可能需要修改时，应最好把它说明为( )参数,以节省参数值的传输时间和存储参数的空间。

A.整形B.引用型C.指针型D.常值引用型·6．向一个长度为n的顺序表中插人一个新元素的平均时间复杂度为( ）。

A．O（n) B．O(1)C．O（n2） D．O（10g2n)二、填空题(每空1分，共28分)1．数据的存储结构被分为——、——、-—和—-四种。

2．在广义表的存储结构中，单元素结点与表元素结点有一个域对应不同，各自分别为——域和——域。

3．-—中缀表达式 3十x＊(2。

4／5—6）所对应的后缀表达式为———-。

4．在一棵高度为h的3叉树中,最多含有——结点。

5．假定一棵二叉树的结点数为18，则它的最小深度为—-,最大深度为-—·6．在一棵二叉搜索树中，每个分支结点的左子树上所有结点的值一定——该结点的值，右子树上所有结点的值一定-—该结点的值。

7．当向一个小根堆插入一个具有最小值的元素时，该元素需要逐层—-调整，直到被调整到——位置为止.8．表示图的三种存储结构为——、——和-——.9．对用邻接矩阵表示的具有n个顶点和e条边的图进行任一种遍历时，其时间复杂度为-—，对用邻接表表示的图进行任一种遍历时，其时间复杂度为—-。

2005-12-19准备题填空题1．顺序表、栈和队列都是_______结构，可以在顺序表的_______位置插入和删除元素；对于栈只能在_______插入和删除元素；对于队列只能在_______插入元素和_______删除元素。

2．由头指针head指向的非空循环单链表，尾结点为p，则head和p满足条件_______________。

3．共H层的完全二叉树至少有个结点，至多有个结点，若按自上而下、从左到右次序给结点编号（从0开始），则编号最小的叶子结点的编号是_________。

4．n个顶点的连通图至少有条边。

5．在无向图G的邻接矩阵A中，若A[i][j]等于1，则A[j][i]等于6．任何一个具有n个结点的无向图的边数小于或等于_______________。

7．任何一个具有n个结点的完全有向图的边数为_______________。

8．排序方法的稳定是指___________________________________。

9．根据数据元素之间的关系，数据在计算机中的存储有两种不同的存储结构，分别是：______存储结构和______存储结构。

10．在数据结构中，数据元素之间通常有下列四类基本结构：______、________、_______和________。

11．通过衡量一个算法的______复杂度和______复杂度来进行判定一个算法的好坏。

12．线性表的最主要的两种应用是______和______，它们之间最重要的区别是：一个是__________、另一个是__________。

13．m*n的稀疏矩阵中，有t个元素不为零，则该矩阵的稀疏因子为______，对于稀疏矩阵，我们通常对其进行______存储。

14．字符串的五种基本操作是：串______、串______、______、串______和______。

15．在二叉树的链式存储结构中，n个结点的二叉链表中有______个空链域。

试卷四一. 填空题（22 分，每空 1 分）1．设待处理的问题规模为n，若一个算法的时间复杂度为一个常数，则表示为（），若一个算法的执行次数为n*log25n，则时间复杂度表示为（）。

2．数据的逻辑结构主要分为（）、（）、（）和（）四种。

3．一棵度为3 的树，若度为1 的结点有5 个，度为2 的结点有8 个，度为3 的结点有12 个，则该树有（）叶子结点。

4．设一个空栈，栈顶指针为1000H，若有输入序列为1、2、3、4、5，经过push、push、pop、push、pop、push、push 后，输出序列是（），若输入的每个数占4 个字节的空间，则栈顶指针为（）H。

5．按照（）遍历二叉排序树得到的序列是一个有序序列。

6．若哈夫曼树一共有n 个叶子结点，则该哈夫曼树总结点数为（）。

7．设C++中存储三维数组A mnp，则第一个元素为a000，若按行优先存储，则a ijk 前面共有（）个元素；若按列优先存储，则a ijk 前面共有（）个元素。

8．设8 行8 列的二维数组起始元素为A[0][0]，按行优先存储到起始元素下标为0 的一维数组B 中，则元素A[5][3]在B 数组中的位置为B[（）]。

9．图的深度优先遍历类似于树的（）遍历，它所用的数据结构是（），图的广度优先遍历类似于树的（）遍历，使用的数据结构是（）。

10．设无向图G 中顶点数为n，则图G 至少有（）边，至多有（）边；若G 为有向图，则至少有（）弧，至多有（）弧。

二. 单选题（23 分，每空 1 分）1.顺序表是一种采用（）存取方式的（）存储结构，链表是一种采用（）存取方式的（）存储结构。

A.顺序B. 随机C.链式D. 有序2．STL 中最常用的用于处理顺序表问题的容器是（），STL 中用于处理链表问题的容器是（）。

A. vectorB. mapC. listD.stack3．长度为20 的有序序列，采用折半查找，共有（）个元素的查找长度为3。

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.edcbaB.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。