《数据结构试题5》由会员分享，可在线阅读，更多相关《数据结构试题5（5页珍藏版）》请在金锄头文库上搜索。
1、GDOU-B-11-302广东海洋大学20082009 学年第一学期数据结构课程试题考试 回5卷 呦闭卷 课程号：1620068姓名题号-二二三四五六七八九十总分阅卷教师各题分数201510202015100实得分数一、填空题（10x2 =20分）1、数据的逻辑结构是指（ ）元素之间（ ）关系的整体。2、抽象数据类型是一个（ ）结构及定义在该结构上的一组（ ）的总称。3、一个非空的线性表可记为 L=（ ）。学号4、入棧时，棧顶指针（ ） 1，出棧时，棧顶指针（ ） 1。5、稀疏矩阵的压缩存储有（ ）和（ ）两种存储。6、广义表（a）,（b）,c）,（d）的长度为（）,深度为（）。7、树中各结点
2、度的（ ）称为该树的（ ）。8、邻接表是一种（ ）与（ ）相结合的存储方法。9、 一棵包含5 0个关键码的3阶B-树，其最小高度为（），最大高度为（）。10、主程序第一次调用递归函数被称为（ ），递归函数自己调用自己被称为（ ） 它们都需要利用（ ）保存调用后的（ ）地址。二、选择题（10x2 =20分）1、A.2、数据的逻辑结构可形式地用一个二元组B=（D,R）来表示，其中D是（）的集 合。数据项 算法指的是（ ）。B.数据对象C.数据元素D.数据类型解决问题的计算方法解决问题的有限运算序列A.计算机程序B.C.排序算法D.下述哪一条是顺序存储结构的优点？（）A.存储密度大B.插入运算方便删
3、除运算方便 D.可方便地用于各种逻辑结构的存储表示 指针的全部作用就是（ ）A.指向某常量B.指向某变量C.指向某结点D.存储某数据5、链表不具有的特点是（ ）3、C.4、A. 插入、删除不需要移动元素 B.可随机访问任一元素C.不必事先估计存储空间D.所需空间与线性长度成正比6、在一个单链表中，若p所指结点不是最后结点，在p之后插入s所指结点, 则执行（ ）。A s-link=p;p-link=s;B s-link=p-link;p-link=s;C s-link=p-link;p=s;D p-link=s;s-link=p;7、设串 sl= Data Structures with Jav
4、a ,s2= it，则子串定位函数 index（sl,s2） 的值为（ ）Al5 Bl6Cl7Dl88、以下说法错误的是 （ ）A. 树形结构的特点是一个结点最多只有一个直接前趋B. 树形结构中的一个结点至多只有一个直接后继C. 树形结构可以表达（组织）更复杂的数据D. 树形结构是一种分支层次结构9、判断一个有向图是否存在回路，除了可以利用拓扑排序方法外，还可以利用（）A.求关键路径的方法B.求最短路径的Dijkstra方法C. 深度优先遍历算法D. 广度优先遍历算法10、在用 Dijkstra 算法求解带权有向图的最短路径问题时，要求图中每条边所 带的权值必须是（ ）。A.非零 B.非整C.
5、非负 D.非正三、判断题（10x2 =20分）1、数据是计算机加工处理的对象。（ ）2、数据的逻辑结构与存储结构都是依赖于计算机的。（ ）3、树的遍历会得到一种线性结构，故非线性结构和线性结构可以相互转换。（ ）4、单链表从任意结点出发都能访问到所有结点。（ ）5、队列是一种先进后出的线性表。（ ）6、串的长度是指串中包含字符的个数。（ ）7、树的最大特点是一对多的层次结构。（ ）8、树中结点的最大度数没有限制，而二叉树的结点的最大度数为 2。（ ）9、图的最小生成树是唯一的。（ ）10、按深度优先搜索遍历图时，与始结点相邻的结点总是先于不于始结点相邻的 结点访问。（ ）四、算法阅读题（4x5
6、 =20分）阅读下面程序，在指定处填空。1、判断队列是否为空template bool LinkQueue:Empty（ ）if（front=（1）return（2）;elsereturn（3）;2、删除栈顶元素 template T LinkStack:Pop( ) Node *p; int x;if (top=(1) throw 下溢 ;x=top-data;/ 暂存栈顶元素p=(2);top=top-next;/将栈顶结点摘链delete (3);return x; 阅读下面程序，指出其算法的功能。3、template void ALGraph:DeleteVex(int i)if (
7、iMaxSize) throw 位置;/顶点输入错误则抛出异常int k;for ( k=0; knext; while(s!=NULL) ArcNode *p;p = s;adjlisti.firstedge-next = s-next;/删除 p 结点/存储顶点信息/顶点数减1s=s-next;delete p; s=adjlisti.firstedge; adjlisti.firstedge=NULL; delete s;for (k=i; kvertexNum; k+) adjlistk=adjlistk+1;vertexNum-;for (k=0; kadjvex i)/ 搜索 i
8、结点s-adjvex-; s = s-next;4、 template T LinkList:Delete(int i)p=first ; j=0; /工作指针 p 初始化while (p & jnext; j+;if (!p | | !p-next) throw 位置; /结点 p 不存在或结点 p 的后继结点不存 在 else q=p-next; x=q-data; /暂存被删结点 p-next=q-next; /摘链 delete q;return x;五、算法设计题（2 5=10 分）1、已知一单链表中的数据元素含有三类字符：字母、数字和其他字符。试编写 算法，构造三个循环链表，使每个
9、循环链表中只含同一类字符。2、设计算法求二叉树的结点个数。六、综合题（10 分）一最小最大堆（min max heap ）是一种特定的堆，其最小层和最大层交替出现， 根总是处于最小层。最小最大堆中的任一结点的关键字值总是在以它为根的子树 中的所有元素中最小（或最大）。如图所示为一最小最大堆；(1) 画出在上图中插入关键字为5 的结点后的最小最大堆。(2) 画出在上图中插入关键字为80 的结点后的最小最大堆；(3) 编写一算法实现最小最大堆的插入功能。假定最小最大堆存放在数组中，关 键字为整数。提示从插入位置进行调整，调整过程由下到上。首先根据元素个数求出插入元 素所在层次数，以确定其插入层是最大层还是最小层。若插入元素在最大层，则 先比较插入元素是否比双亲小，如是，则先交换，之后，将小堆与祖先调堆，直 到满足小堆定义或到达根结点；若插入元素不小于双亲，则调大堆，直到满足大 堆定义。若插入结点在最小层，则先比较插入元素是否比双亲大，如是，则先交 换，之后，将大堆与祖先调堆；若插入结点在最小层且小于双亲，则将小堆与祖 先调堆，直到满足小堆定义或到达根结点。
