大工19秋《数据结构》期末考试复习题
- 格式：docx
- 大小：93.61 KB
- 文档页数：8
机密★启用前大连理工大学网络教育学院2019年秋《数据结构》期末考试复习题☆注意事项：本复习题满分共：200分。
一、单项选择题1、在队列中存取数据的原则是（）。
A．先进先出B．后进先出C．先进后出D．随意进出2、在下列链表中，不能从当前结点出发访问到其余各结点的是（）。
A．单链表B．单循环链表C．双向链表D．双向循环链表3、在一棵二叉树上第5层的结点数最多为（）设树根为第1层。
A．16 B．15 C．8 D．324、一棵有124叶子结点的完全二叉树，最多有（）个结点。
A．247 B．249 C．248 D．1255、具有10个叶子结点的二叉树中有（）个度为2的结点。
A．8 B．9 C．10 D．116、若一棵二叉树的先序遍历序列为abdgcefh，中序遍历的序列为dgbaechf，则后序遍历的结果为（）。
A．gdbehfca B．bdgaechfC．gdbecfha D．gcefhabd7、对线性表进行顺序查找时，要求线性表的存储结构是（）。
A．倒排表B．索引表C．顺序表或链表D．散列表8、对于顺序存储的有序表(5,12,20,26,37,42,46,50,64),若采用折半查找，则查找元素26的查找长度为（）。
A．2 B．3 C．4 D．59、在所有排序方法中，关键字比较的次数与记录的初始排序次序无关的是（）。
A．希尔排序B．起泡排序C．插入排序D．选择排序10、堆的形状是一棵（）。
A．二叉排序树B．满二叉树C．完全二叉树D．平衡二叉树11、线性表采用顺序存储结构时，其地址（）。
A．必须是连续的B．部分地址必须是连续的C．一定是不连续的D．连续与否均可以12、在栈中存取数据的原则是（）。
A．先进先出B．后进先出C．后进后出D．随意进出13、插入和删除只能在一端进行的线性表，称为（）。
A．队列B．循环队列C．栈D．数组14、一个基本线性表的第一个元素的存储地址是100，每个元素的长度是2，则第5个元素的地址是（）。
A．110 B．108 C．100 D．12015、算法分析的目的（）。
A．找出数据结构的合理性B．研究算法中的输入与输出的关系C．分析算法的效率以求改进D．分析算法的易懂性和文档性16、结点前序为xyz的不同二叉树，那么它有（）种不同状态。
A．3 B．4 C．5 D．617、将一棵有100个结点的完全二叉树从上到下，从左到右依次对结点进行编号，根结点的编号为1，则编号为49的结点的左孩子编号为（）。
A．98 B．99 C．50 D．4818、设高度为h的二叉树上只有度为0和度为2的结点，则此类二叉树中所包含的结点数至少为（），设根结点的所在高度为1。
A．2h B．2h-1C．2h+1 D．h+119、在一个具有n个顶点的无向图中，要连通全部顶点至少需要（）条边。
A．n B．n+1C．n-1 D．n/220、存储在磁带上的顺序文件的查找只能用（）。
A．顺序查找B．二分查找C．分块查找D．树表查找单选题答案1． A 2． A 3． A 4． C 5． B6． A 7． C 8． C 9． D 10． C11． A 12．B 13．C 14．B 15． C16． C 17．A 18．B 19．C 20． A二、填空题1、一个算法有五个特性：_______、_______、_______、有零个或多个输入、有一个或多个输出。
2、栈S在进行出栈操作时首先要判断_______。
3、在一棵二叉树中，度为零的结点的个数为n0，度为2的结点的个数为n2，则有n0=_______。
4、设front为队首指针，rear为队尾指针，则循环队列sq是空队列的条件是_______。
5、同一数组中各元素的长度_______。
6、深度为k的二叉树共有2k-1个结点，该二叉树为_______二叉树。
7、若图G中每条边都_______方向，则称G为无向图。
8、二叉树的按层次遍历类似于图的_______遍历。
9、选择排序算法的效率为_______。
10、冒泡排序算法的效率为_______。
答案：1、有穷性、确定性、可行性2、栈空否3、n2+14、sq->rear==sq->front5、相等6、满7、没有8、广度优先9、O(nlogn)10、O(n2)三、判断题1、数组的缺点是插入、删除运算效率低。
（ √ ）2、链表的优点是插入、删除运算效率高。
（ √ ）3、对图进行深度优先遍历时，应借助于一个队列。
（ × ）4、二叉树的深度优先遍历与先序序列一致。
（ √ ）5、归并排序算法是原地算法。
( × )6、堆数据结构可以看作是一个非完全二叉树。
( × )7、对图进行广度优先遍历时，应借助于一个队列。
（ √ ）8、二叉树的深度优先遍历与后序序列一致。
（ × ）9、对图进行广度优先遍历时，应借助于一个栈。
（ × ）10、冒泡排序算法是原地算法。
( √ )四、 简答题1、初始为空的队列中，元素f,e,d,c,b,a 依次进队以后，连续进行了三次出队操作，此时的队首元素是什么？队尾元素是什么？队列操作应遵循的原则是什么？答：（1） 队首元素是c（2） 队尾元素是a（3） 队列操作应遵循的原则是先进先出2、画出按24,33,61,23,27,5,38,72,12输入键值所建立的二叉搜索树； 计算在等概率的情况下，该二叉搜索树查找成功的平均检索长度；画出在已构造好的二叉搜索树中依次删除结点24后的二叉搜索树。
(1) 建立的二叉搜索树为 (2) 平均检索长度为 (0+1*2+2*3+3*3)/9 = 1.89 (3) 删除节点24之后，二叉搜索树变为2423512 38 33 27 61 723、写出用直接插入法排序将数值序列{33,23,8,41,68,64,50}排序过程的每一趟结果。
23 33 8 41 68 64 508 23 33 41 68 64 508 23 33 41 68 64 508 23 33 41 68 64 508 23 33 41 64 68 508 23 33 41 50 64 68 4、什么是稳定排序？插入法排序是稳定排序吗？简述是或不是的具体原因。
什么是原地排序？冒泡法排序是原地排序吗？简述是或不是的具体原因。
答：插入法是稳定排序。
因为在排序过程中新的元素都要放到相等值的右面，因此与在原始序列中出现的顺序相同。
原地排序意味着在排序过程中不需要使用额外的内存。
冒泡法是原地排序，因为排序过程都是在原始数组上进行两两交换，不需要额外的内存。
5、给出下图所示的无向图的邻接矩阵表示，然后写出依据此邻接矩阵从顶点3开始对图分别进行深度优先遍历的序列及所得的深度优先生成树。
答：邻接矩阵 1,1,1,1,11,1,0,1,11,0,1,1,01,1,1,1,01,1,0,0,1深度优先遍历序列 3,1,2,4,5272351238 33 61 72 41 2 3 5深度优先生成树6、简述逻辑结构和存储结构的关系。
答：在数据结构中，逻辑结构与计算机无关，存储结构是数据元素之间的逻辑关系在计算机中的表示。
存储结构不仅将逻辑结构中所有数据元素存储到计算机内存中，而且还要在内存中存储各种数据元素间的逻辑关系。
通常情况下，一种逻辑结构可以有多种存储结构，例如，线性结构可以采用顺序存储或链式存储结构表示。
7、简述线性表、栈和队列的异同。
答：线性表、栈和队列中元素这之间的逻辑关系都是线性关系。
栈和队列是操作位置受限的线性表，即对播入和删除操作的位置加以限制，都只能在端点进行。
栈是仅允许在表的一端进行插入和删除操作的线性表，因而是后进先出表。
队列是只允许在表的一端进行插入，另一端进行删除操作的线性表，因而是先进先出表。
8、堆排序是否是一种稳定的排序方法？为什么？答：堆排序是不种不稳定的排序方法。
因为在堆的调整过程中，关键字进行比较和交换所走的是该节点到叶子节点的一条路径，因此对相同的关键字而言，就可能出现排在后面的关键字补交换到前面来的情况。
9、顺序存储适用于何种二叉树？答：适用于完全二叉树，可充分利用存储，并可方便地找到某结点的双亲结点、兄弟和子女。
10、给出关键字序列{4，5，1，2，8，6，7，3，10，9}的希尔排序过程。
答案：排序前4，5，1，2，8，6，7，3，10，9gap=5 4，5，1，2，8，6，7，3，10，9gap=2 1，2，4，3，7，5，8，6，10，9gap=1 1，2，3，4，5，6，7，8，9，10排序后1，2，3，4，5，6，7，8，9，10五、算法题1、简述冒泡排序算法的思想，并通过类Ｃ语言给出代码实现。
算法思想1）不停地比较相邻的记录，如果不满足排序要求，就交换相邻记录，直到所有的记录都已经排好序。
2）检查每次冒泡过程中是否发生过交换，如果没有，则表明整个数组已经排好序了，排序结束。
void BubbleSort(Record Array[], int n) {bool NoSwap;// 是否发生了交换的标志int i, j;for (i = 0; i < n-1; i++) {NoSwap = true;// 标志初始为真for (j = n-1; j > i; j--)if (Array[j] < Array[j-1]) { // 判断是否逆置swap(Array, j, j-1);// 交换逆置对NoSwap = false;// 发生了交换，标志变为假}if (NoSwap) // 没发生交换，则排好序return;}}2、简述直接选择排序算法的思想，并用类Ｃ语言给出算法实现。
算法思想：选出未排序记录中的最小记录，然后直接与未排序序列中第1个记录交换。
void SelectSort(Record Array[], int n) {// 依次选出第i小的记录，即剩余记录中最小的那个for (int i=0; i<n-1; i++) {// 首先假设记录i就是最小的int Smallest = i;// 开始向后扫描所有剩余记录for (int j=i+1;j<n; j++)// 如果发现更小的记录，记录它的位置if (Array[j] < Array[Smallest])Smallest = j;//将第i小的记录放在数组中第i个位置Record temp = Array[Smallest];Array[Smallest]= Array[i];Array[i]= temp;}}3、简述直接插入排序算法的思想，并通过类Ｃ语言给出代码实现。
算法思想:利用有序表的插入操作进行排序void InsertSort (Record Array[], int n) {//Array[]为待排序数组，n为数组长度Record TempRecord;// 临时变量for (int i=1; i<n; i++) {// 依次插入第i个记录TempRecord = Array[i];//从i开始往前寻找记录i的正确位置int j = i-1;//将那些大于等于记录i的记录后移while ((j>=0) && (TempRecord < Array[j])) {Array[j+1] = Array[j];j = j - 1;}//此时j后面就是记录i的正确位置，回填Array[j+1] = TempRecord;}}。
