数据结构期末考试试题和标准答案及评分标准

数据结构问题(a卷)(试验时间： 90分钟)一、个别选题(本大题共15小题，每小题2分，共30分)(每个问题只有一个选项是正确的，请将答案括在括号中，不要错误地选择或多次选择。)1.()是构成数据的基本单位，是数据整体相对独立的单元。a .数据b .数据元素c .数据对象d .数据结构2 .算法计算量的大小称为算法的()a .效率b .复杂度c .数据要素间关系d .数据的存储方法3 .如果线性表中最常见的操作是访问具有指定编号的元素，最后插入或删除元素，则以下()方法可节省最多的时间：a .链存储b .索引存储c .顺序存储d .散列存储4 .以下哪一项是顺序存储结构的优点？ （）a .记忆密度大的b .插入运算容易c .删除运算方便d .可方便地用于各种逻辑结构的存储显示5 .如果在一个链路表中删除由p指定的节点的后续节点，执行()a.p-next=p-next-nextb.p-next=p-nextC.p=p-next； p-next=p-next-nextd.p=p-next-next6 .开头节点的单链表head为空的判定条件为()a.head=nul Rb.head-next=nullc.head-next=headd.head！=NULL7 .非空循环链路表头的末尾节点(用p指示)满足()a.p-head=nullb.p=nullc.p-next=headd.p=head8 .以下关于线性表的描述中，哪个是错误的？ （）a .线性表采用顺序存储，必须占用连续的存储单元。b .线性表采用逐次记忆，易于插入和删除。c .线性表采用链式记忆，无需占用连续的记忆单元。d .线性表采用链式记忆，易于插入和删除。9 .队列操作的原则是()a .后进先出b .先进先出c .仅插入d .仅删除10 .堆栈中允许插入和删除的一侧称为()a .栈头b .栈尾c .栈顶d .栈底11 .以阵列An存储循环队列的要素，若将其首尾指针分别设为front和rear，则当前队列的要素数为()A.(rear-front n)%n B. rear-front 1c.(前读) % nd.(前读) % n12 .在最大容量为n的循环队列、尾指针为rear、开头指针为front的情况下，空闲的判断条件为()a.(rear1) % n=frontb.rear=frontc.rear1=frontd.(rear-1 ) % n=front13 .要将十进制数转换为二进制数，请使用以下数据结构()a .图b .木c .广义表d .堆14 .把一棵树变成二叉树后，该二叉树的形态为()a .两类b.3类c.4类d .唯一的15 .左右子树不空的二叉树先被线索化后，其中空锁域的数量为()A. 3 B. 2 C. 0 D .不明二、填空问题(本大题共十个空，一个空两分，共二十分)1、数据结构是研究程序设计中计算机操作及其关系和计算的学科。2 .在一个链接表中，已知指针q指向的节点是指针p指向的节点的前驱节点，如果在q与p之间插入节点s，则执行两句话。 _ _。3 .字符串是指采用节点大小为2的链接表作为其存储结构，仅存储链接表的各链接点的域变成了两个字。4 .广义表(a、b、c、d )的末尾是：5 .深度k的二叉树，最多也有节点。6 .已知有向图G=(V，e )， V=v1，v2，v3，v4，v5，v6，v7；e=，g的拓扑序列是_。7 .具有n个顶点的连通图至少有边。8 .图的记忆常采用两种方法。三、判断问题(本大问题共十小问题，每题一分，共十分)(请在每个小题后面的括号里写上答案。 如果正确的话请写“”。 如果你错了，那就说：好的。1 .如果使用链路表示存储线性表示，则节点与节点内的存储空间可以是不连续的。 （）2 .线性表是按顺序存储的表。 （）3 .线性表元素总数基本稳定，插入和删除操作较少，但需要以最快的速度访问线性表元素时，应采用顺序存储结构。 （）4 .线性表的连锁存储结构所需的存储空间通常比顺序存储结构多。 （）5 .字符串的长度是指字符串中包含的不同字符数。 （）6 .压缩和存储稀疏矩阵的目的是节省存储空间。 （）7 .因为二叉树是非线性数据结构，所以无法使用顺序存储结构来进行存储。 （）8 .任何一个二叉树中至少一个节点的度为2。 （）9 .在线性表的检索中，线性必须按顺序存储，节点必须按关键字顺序排序。 （）10 .采用线性搜索方法解决冲突问题，产生的一系列后续哈希地址必须大于或等于原始哈希地址。 （）四、应用问题(本小题共5小题，每小题6分，共30分)1 .简要叙述以下算法的功能(假设堆栈和队列的要素类型为int ) (6点)。void fun1(Queue Q )堆栈s；int x；Initstack(S )While (！ QueueEmpty(Q ) ) DeQueue(Q，x )；推(s，x )以下While (！ 堆栈空间(s ) ) Pop(S，x )；EnQueue(Q，x )以下以下称为2 .请把图4.1那样的树换成二叉树。 (6分)图4.1树3 .给定的叶节点(a、b、c、d、e、f、g )和权重分别在2- 3，12，15，7，17，2，8 处绘制相应的霍夫曼树，并写入每个叶节点的霍夫曼代码。 (6分)4.(6点)已知的图g的邻接表示在图4.2中，如下所示从顶点v1开始的深度优先搜索序列是_ _ _。从顶点v1开始的宽度优先搜索序列是_。图4.2图g邻接表秘密封上信线秘密封上信线5 .结构图求出4.3所示的无向网的最小生成树(6点)图4.3无向网五、算法设计问题(本大题共1小题，每小题10分，共10分)。1 .已知查找表的数据元素类型如下：类型结构恢复int num；char name8；Rectype；假设查找表包含n条记录，并且以num降序存储Typedef Rectype Sqlist100；要求： (1)写入二分搜索给定值k的算法和main函数。(2)二分搜索算法的函数头是“int binsearch(Sqlist R，int n，int K )”(在main函数中制作该查找表，调用二分搜索算法，输出搜索结果。数据结构问题(b卷)(试验时间： 90分钟)一、个别选题(本大题共15小题，每小题2分，共30分)(每个问题只有一个选项是正确的，请将答案括在括号中，不要错误地选择或多次选择。)1 .在数据结构中，数据的()结构独立于计算机。a .逻辑b .存储器c .散列d .索引2 .下一段的时间复杂性为()for(i=0； inext=headC.head-next=NULL D.head！=NULL5 .在线性表是序列结构的情况下，请求在存储器内可使用的存储单元的地址()a .不连续的b .部分地址一定是连续的c .必须连续的d .不必连续的6 .在单链表中，两个节点之间插入了需要修改的指针。A.0B.1 C.2 D.47 .如果线性表具有n个要素，则在单链路表中实现算法()比在顺序表中实现算法更高效。a .删除具有x值的所有元素b。 在最后一个元素后面插入一个新元素c .依次输出前k个元素d。 交换其中一个元素的值8 .在顺序表中，访问节点和增量删除节点的时间复杂度分别为()a.o (n ) o (n ) b.o (1) o (n ) c.o (n ) o (1) d.o (1) o (1)9 .删除队列的操作在()中进行。a .队首b .队尾c .队首前单元d .队尾后单元10 .在关于以下堆栈的描述中，正确的是()a .堆底的要素必须是最后进入堆的要素b .堆操作遵循先进的后退原则c .堆栈顶端的要素必定是最初进入堆栈的要素d .以上的3个表现错误11 .如果将堆栈s与队列q的初始状态置空，且元素e1、e2、e3、e4、e5和e6依次进入堆栈s，一个元素在堆栈之后进入q，并且六个元素退出队列的序列是e2、e4、e3、e6、e5和e1，则堆栈s的容量至少为()个。A.3 B. 4 C.5 D.612 .假定分配给循环队列的向量空间为Q20，并且如果队列的长度和队列的第一个指针的值分别为13和17，则当前末尾指针的值为_。A.10 B.11 C.12 D.1313 .银行业务呼叫系统采用了数据结构。a .堆栈b .广义表c .队列d .图14 .根据二叉树的定义，具有3个节点的不同形状的二叉树有_种。A.3B.4 C.5 D.615. n个节点的线索二叉树中包含的线索数是_。A.0B.n-1 C.n 1 D.2n二、填空问题(本大题共十个空，一个空两分，共二十分)1 .数据结构包括三个方面：数据逻辑结构、数据结构和对数据执行的操作。2 .如果发现指针q的值为NULL且指针p指向链接表l中的一个节点，则删除后续节点(希望用指针q指向)的字符为，free(q )。3 .广义表L=(a，() 时，Head(L)=。4 .只有在两个字符串相等、各自对应位置的字符相等的情况下，两个字符串才相等。5 .二叉树的第4层节点数最大为个。6 .除了求关键路径的方法外，还可以用方法判断定向图中是否存在循环(循环)。7 .图的扫描主要有两种方法。8 .具有四个顶点的无向完整图有边缘。三、判断问题(本大问题共十小问题，每题一分，共十分)(请在每个小题后面的括号里写上答案。 如果正确的话请写“”。 如果你错了，那就说：好的。1 .对于一个线性表，采用逐级存储方式插入或删除节点效率低下，采用链存储方式较好。 （）2 .静态链表是指始终保持不变的链表。 （）3 .在顺序表中，最后一个要素是后面的。 （）4 .线性表是连锁存储的表。 （）5 .字符串是一种特殊的线性表，其特殊性能够在数据元素中表示多个字符。 （）6 .压缩和存储稀疏矩阵的目的是便于输入和输出。 （）7 .任何二叉树中的度可以小于2。 （）8 .树结构最适合于表示要素之间存在分支层次关系的数据。 （）9 .在采用区块搜索的情况下，数据被分成几个区块，各区块内的数据必须有秩序。 （）10 .序列搜索法适用于存储结构为序列存储或链存储的线性表。 （）四、应用问题(本小题共5小题