中 原 工 学 院 信 息 商 务 学 院 重修标识 2006～2007 学年 第 二 学期 A卷 软件、网络 专业 数据结构 课程期末试卷
一、 单项选择题 (本大题共10小题，每小题2分，共30分) 1. 计算机算法指的是（ ）。 A．程序 B．问题求解步骤的描述 C．调度方法 D．排序方法 2. 以下数据结构中，（ ）个是非线性数据结构。 A．树 B．字符串 C．队 D．栈 A．O(n) O(n) B．O(n) O(1) C．O(1) O(n) D．O(1) O(1) 4. 在单链表指针为p的结点之后插入指针为s的结点，正确的操作是（ ）。 A.p->next=s;s->next=p->next B.s->next=p->next; p->next=s C.p->next=s;p->next=s->next D.p->next=s->next; p->next=s 5. n个顶点的有向图中,含有向边的数目最多为( ) A．n-1 B．n C．n(n-1)/2 D．n(n-1) 6. 循环队列存储在数组]中，则入队时的操作为（ ） A．rear=rear+1 B．rear=(rear+1)mod(m-1) C． rear=(rear+1)mod m D． rear=(rear+1)mod(m+1) | 7. 字符串’ababaabab’的next函数为（ ） A.011232232 B.012341234 C.011122334 D. 011234234 A．9 B．11 C．15 D．不确定 9. 设有数组A[i,j]，数组的每个元素长度为3字节，i的值为1到8，j的值为1到10，数组从内存首地址BA开始顺序存放，当以列为主序存放时，元素 A[5,8]的首地址为（ ）。 A．BA+141 B．BA+180 C．BA+222 D．BA+225 10. n个顶点的带权无向连通图的最小生成树包含( )个顶点 A．n-1 B．n C．n/2 D．n+1 11．有关二叉树的下列说法正确的是（ ） A．二叉树的度为2 B．一棵二叉树的度可以小于2 C．二叉树中至少有一个结点的度为2 D．二叉树中任何一个结点的度都为2 12．关键路径是AOE网中（ ）。 A．从源点到汇点的最长路径 B．从源点到汇点的最短路径 C．最长回路 D．最短路径 13．若查每个记录的概率相等，则在具有n个记录的连续文件中采用顺序查查一个记录，其平均查长度ASL为（ ）。 A．(n-1)/2 B．n/2 C．(n+1)/2 D．n 14．就平均性能而言，目前最好的内部排序方法是（ ） A．冒泡排序 B．希尔排序 C．堆排序 D．快速排序 15．已知广义表LS=((a,b,c),(d,e,f))，运用head和tail函数取出LS中原子e的运算是（ ）。 A．head(tail(LS)) B．tail (head (LS)) C．head(tail(head(tail(LS)))) D．head(tail(tail (head (LS)))) | ||||||||||||||||||||||||||||||||||||
二、填空题 (本大题共10小题，每空2分，共20分) 1. 数据的物理结构包括 的表示和 的表示。 2. 带头结点的单循环链表L中只有一个元素结点的条件是 。3. 在队列中，允许进行插入操作的一端称为____________，允许进行删除操作的一端称为____________。 4. 串中所含字符个数称为该串的_______________。 5. 深度为h的完全二叉树至少有 个结点，至多有 个结点。 6. 对关键字序列(52，80，63，44，48，91)进行一趟快速排序之后得到的结果为 。 7．有n个顶点的有向图，至少需要 条弧才能保证是连通的。 三．算法设计题（10三维景点分） 假设以带头结点的单循环链表表示队列，其中结点结构为（data，next），并且只设一个指针rear指向队尾结点，但不设头指针，请写出相应的入队：EnQueue(Li nkList &rear,ElemType x)和出队 DeQueue(Li nkList &rear,ElemType &x)算法。 | 四、应用题 1．设一数列输入顺序为123456，若采用栈结构，能否得到输出顺序为325641和154623的序列，并说明为什么不能得到或者如何得到（即写出以‘S’表示进栈和以‘X’表示出栈的栈操作序列）。（8分） 2．已知一棵二叉树的前序遍历的结果是ABDFCEGH，中序遍历的结果是BFDAGEHC， （1）画出这棵二叉树；（4分） （2）画出这颗二叉树的后序线索树；（3分） （3）将这颗二叉树转换成对应的树（或森林）。 （3分） |
3．将如下所示的有向图给出其存储结构的邻接链表表示（注：这里顶点的邻接点按升序排列），然后分别写出对其邻接表从顶点双扣管1开始进行深度优先遍历序列和广度优先遍历序列的结果。（画出邻接链表4分，求出深度优先序列和广度优先序列各3分，共10分） | 4．给定关键码序列（26，25，20，33，21，24，45，204，42，38，29，31），要用哈希法进行存储，规定装填因子a=0.6 （1）请给出除留余数法的哈希函数；（4分） （2）用线性探测法解决冲突，请画出插入所有的关键码后得到的哈希表；（5分） （3）计算等概率情况下查成功的平均查长度。（3分） |
A透气盖卷 中 原 工 学 院 信 息 商 务 学 院 2006～2007学年 第 2 学期 软件、网络专业 数据结构 课程期末试卷标准答案（即评分标准） 一、单选题(每小题2分，共30分)
二、填空题(每空2分，共20分) 1．数据元素 关系 2. L->next->next==L 3．队尾 队头 4． 长度 5. 2h-1 2h-1 6．48 44 52 63 80 91 7．n 三、算法设计题：（共10分） 参考算法： void EnQueue(LinkList &rear,ElemType x) { s=new LNode;//1分 if(!s) exit(1); s->data=x;s->next=rear->next;//2分 rear->next=s;rear=s;//2分 } void DeQueue(LinkList &rear,ElemType &x) { if(rear->next==rear) exit(1);//1分 s=rear->next->next;x=s->data; //2分 rear->next->next=s->next //1分 if(s==rear)rear=rear->next;//1分 delete s; } | 四、 应用题 1、（共8分） 能得到325641，（2分） S(1)S(2) S(3)X(3)X(2)S(4)S(5)X(5)S(6)X(6)X(4)X(1)（2分） 不能得到154623（2分） S(1)X(1)S(2) S(3) S(4)S5) X(5)X(4)S(6)X(6),此时，栈中还有23，所以不会得到23，只能得到32（2分） 2、（共10分） （1）（4分） （2）（3分） （3）（3分） | ||||||||||||||||||||||||||||||
3、(共10分。其中：邻接链表4分，深度和广度优先遍历序列各3分) 深度优先遍历序列：125967384 广度优先遍历序列：123456789 | 4、 (共12分) （1）(4分)表长m=12/0.6=20，H(key)=key MOD 19 （2）（5分） H（26）=7 成功 H（25）=6 成功 H（20）=1 成功 H（33）=14 成功 H（21）=2 成功 H（24）=5 成功 H（45）=7 冲突 H1（45）=8 成功 H（204）=14 冲突 H1（204）=15 成功 H（42）=4 成功 H（38）=0 成功 H（29）=10成功 H（31）=12 成功
(3) （3分） 在等概率的情况下，查成功时的平均查长度 ASLsucc = ( 1 *10+2*2 ) / 12 = 14 / 12 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
本文发布于:2024-09-22 14:23:02，感谢您对本站的认可！
本文链接：https://www.17tex.com/tex/4/171136.html
版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系，我们将在24小时内删除。
| 留言与评论（共有 0 条评论） |
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议