数据结构-大连理工2022年春期末考试复习题

第第#页共7页20、存储在磁带上的顺序文件的查找只能用( )。B.二分查找D.树表查找1．A2．A3．6．B.二分查找D.树表查找1．A2．A3．6．A7．C8．11．A12．B13．16．C17．A18．A4．C5．BC9．D10．CC14．B15．CB19．C20．A二、填空题1、一个算法有五个特性： 、 、 、有零个或多个输入、有一个或多个输出。2、栈S在进行出栈操作时首先要判断3、在一棵二叉树中，度为零的结点的个数为n0,度为2的结点的个数为4,则有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)三、判断题1、数组的缺点是插入、删除运算效率低。（d）2、链表的优点是插入、删除运算效率高。（d）3、对图进行深度优先遍历时，应借助于一个队列。（x）4、二叉树的深度优先遍历与先序序列一致。（d）5、归并排序算法是原地算法。（x）6、堆数据结构可以看作是一个非完全二叉树。（x）7、对图进行广度优先遍历时，应借助于一个队列。（d）8、二叉树的深度优先遍历与后序序列一致。（x）9、对图进行广度优先遍历时，应借助于一个栈。（x）10、冒泡排序算法是原地算法。（d）四、简答题1、初始为空的队列中，元素f,e,d,c,b,a依次进队以后，连续进行了三次出队操作，此时的队首元素是什么？队尾元素是什么？队列操作应遵循的原则是什么？答：队首元素是c队尾元素是a队列操作应遵循的原则是先进先出2、当为解决某一问题而选择数据结构时，应从哪些方法考虑？答：通常从两方法考虑；第一是算法所需的存储空间量，第二是算法所需的时间。对算法所需的时又涉及以下几点：1）程序运行时所需输入的数据总量2）计算机执行每条指令所需的时间3）程序中指令重复执行的次数3、写出用直接插入法排序将数值序列｛33,23,8,41,68,64,50｝排序过程的每一趟结果。答：（1）2333841686450（2）8233341686450（3）8233341686450（4）8233341686450（5）8233341646850（6）82333415064684、简述顺序表特点。答：优点：可随机存取表中任意数据元素，算法简单，空间利用率高；直接可获取线性表的长度。缺点：1）需要预先确定数据元素的最大个数；2）数据元素的插入、删除相对麻烦，插入和删除时需要移动较多的数据元素。5、简述逻辑结构和存储结构的关系。答：在数据结构中，逻辑结构与计算机无关，存储结构是数据元素之间的逻辑关系在计算机中的表示。存储结构不仅将逻辑结构中所有数据元素存储到计算机内存中，而且还要在内存中存储各种数据元素间的逻辑关系。通常情况下，一种逻辑结构可以有多种存储结构，例如，线性结构可以采用顺序存储或链式存储结构表示。6、简述线性表、栈和队列的异同。答：线性表、栈和队列中元素这之间的逻辑关系都是线性关系。栈和队列是操作位置受限的线性表，即对播入和删除操作的位置加以限制，都只能在端点进行。栈是仅允许在表的一端进行插入和删除操作的线性表，因而是后进先出表。队列是只允许在表的一端进行插入，另一端进行删除操作的线性表，因而是先进先出表。7、堆排序是否是一种稳定的排序方法？为什么？答：堆排序是不种不稳定的排序方法。因为在堆的调整过程中，关键字进行比较和交换所走的是该节点到叶子节点的一条路径，因此对相同的关键字而言，就可能出现排在后面的关键字补交换到前面来的情况。8、若频繁地对一个线性表进行插入和删除操作，该线性表宜采用何种存储结构，为什么？答：宜采用链式存储结构。因为采用链式结构存储线性表，在插入和删除操作时只修改相关节点的指针域，不需要移动节点；而采用顺序结构存储线性表，插入和删除操作需要平均移动表中的一半元素。修改指针域操作比移动元素操作花费的时间少得多。9、对单链表设置头节点的作用是什么？答：对于带头节点的单链表，在单链表的任何节点之前插入节点或删除节点，所要做的都是修改前一个节点的指针域，因为任何节点都有前驱节点（若单链表没有头节点，则首节点没有前驱节点，在其前插入节点和删除节点时操作复杂些）。对于带头节点的链表，在表空时也存在一个头节点，因此空表与非空表的处理是一样的。五、算法题1、简述冒泡排序算法的思想，并通过类C语言给出代码实现。算法思想1)不停地比较相邻的记录，如果不满足排序要求，就交换相邻记录，直到所有的记录都已经排好序。2)检查每次冒泡过程中是否发生过交换，如果没有，则表明整个数组已经排好序了，排序结束。voidBubbleSort(RecordArray[],intn){boolNoSwap; //是否发生了交换的标志inti,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、简述直接选择排序算法的思想，并用类C语言给出算法实现。算法思想：选出未排序记录中的最小记录，然后直接与未排序序列中第1个记录交换。voidSelectSort(RecordArray[],intn){//依次选出第i小的记录，即剩余记录中最小的那个for(inti=0;i<n-1;i++){//首先假设记录i就是最小的intSmallest=i;//开始向后扫描所有剩余记录for(intj=i+1;j<n;j++)//如果发现更小的记录，记录它的位置if(Array[j]<Array[Smallest])Smallest=j;//将第i小的记录放在数组中第i个位置Recordtemp=Array[Smallest];Array[Smallest]=Array[i];Array[i]=temp;}}3、简述直接插入排序算法的思想，并通过类C语言给出代码实现。算法思想:利用有序表的插入操作进行排序voidInsertSort(RecordArray[],intn){//Array口为待排序数组，n为数组长度RecordTempRecord;//临时变量for(inti=1;i<n;i++){//依次插入第i个记录TempRecord=Array[i];〃从i开始往前寻找记录