数据结构期末样卷(含答案).doc

数据结构期末样卷 一 单项选择题( 10分)1线性表逻辑顺序与存储顺序总是一致的，这种说法 A 。A 正确 B 不正确2. 在一个单链表中，已知q所指结点是p所指结点的前驱结点，若在q和p之间插入s结点，则执行 。A. s-next=p-next; p-next=s; B. p-next=s-next; s-next=p;C. q-next=s; s-next=p; D. p-next=s; s-next=q;3一个栈的入栈序列是a，b，c，d，e，则栈的不可能的输出序列是_。Ae d c b a Bd e c b a Cd c e a b Da b c d e4判定一个循环队列QU（最多元素为m0）为满队列的条件是 。AQU-front=QU-rear BQU-front！=QU-rearCQU-front=（QU-rear+1）m0 (不是很确定) DQU-front!=（QU-rear+1）m05串是一种特殊的线性表，其特殊性体现在_。A可以顺序存储 B.数据元素是一个字符C可以链接存储 D.数据元素可以是多个字符6一棵非空的二叉树的先序遍历序列与后序遍历序列正好相反，则该二叉树一定满足_。 A. 所有的结点均无左孩子 B. 所有的结点均无右孩子 C. 只有一个叶子结点 D. 是任意一棵二叉树7若采用三元组压缩技术存储稀疏矩阵，只要把每个元素的行下标和列下标互换，就完成了对该矩阵的转置运算，这种观点 。A正确 B错误 8广义表(a，b，c，d)的表头是 ，表尾是 。Aa B( ) C(a，b，c，d) D(a，b，c，d) 9一组记录的排序码为（46，79，56，38，40，84），则利用堆排序的方法建立的初始堆为 。A79，46，56，38，40，80 B. 84，79，56，38，40，46C. 84，79，56，46，40，38 D. 84，56，79，40，46，3810用某种排序方法对线性表（25，84，21，47，15，27，68，35，20）进行排序时，元素序列的变换情况如下：（1）25，84，21，47，15，27，68，35，20（2）20，15，21，25，47，27，68，35，84（3）15，20，21，25，35，27，47，68，84（4）15，20，21，25，27，35，47，68，84则所采用的排序方法是 。A. 选择排序 B. 希尔排序 C. 归并排序 D.快速排序二填空题( 20分)1下面程序段的时间复杂度是 O(n2) 。for (i=0;in;i+) for (j=0;jnext ) Q=L; L=L-next; P=L; While ( P-next ) P=P-next; P-next=Q; Q-next=NULL;return OK; /A /形成一个循环链表2简述以下算法的功能（5分）。 status algo2 (Stack S，int e) Stack T； int d；InitStack (T)；while ( !StackEmpty (S) ) Pop ( S，d)； if (d!=e) Push (T，d )； while ( !StackEmpty (S) ) Pop ( T，d)； /这里应该有点问题 把S 改成T （我自己认为） Push ( S，d)； 将堆栈S中的为e的值去掉。（T充当临时存放的堆栈）3设给定权集w =1，23，14，7，28，9，试构造关于 w的一棵赫夫曼树，并求其加权路径长度 WPL。（10分）4请对下图的无向带权图，写出它的邻接表，并按克鲁斯卡尔/Prim算法求其最小生成树（10分）。 5设散列表的长度=13；散列函数为H(K)=K mod m，给定的关键码序列为20，21，14，68，19，23，30，1，84，15，27，79，试画出用线性探测再散列法解决冲突时所构造的散列表。并求出在等概率的情况下，这种方法搜索成功时的平均搜索长度。 012345678910111214168301519202184232779平均搜索长度=40/12=3.36. 已知序列583，87，512，61，908，170，897，275，623，462，采用基数排序法对该序列作升序排序时的每一趟的结果（10分）。 170 61 462 512 623 583 275 87 897 908四算法设计题( 20分)1设顺序表va中的数据元素递增有序。试写一算法，将x插入到顺序表的适当位置上，以保持该表的有序性。 Int Intsert（SqList * va,datatype x） If(va-length=MAXSIZE) rerurn ERROR; int k = va-Length;for(int i=0;iLength;i+) if(va-dataix) k=i;break;For(int j=va-length-1;jk-1;j-) va-dataj+1=va-dataj;Va-datak= x;Va-length+; Return OK;2 假设以带头结点的循环链表表示队列，并且只设一个指针指向队尾元素结点(注意不设头指针)，试编写相应的队列初始化、入队列的算法。typedef struct N0deint data; struct N0de *next;N0de,*QueuePtr;typedef struct QueuePtr rear; SqListVoid InitalSql(SqList *Q) /初始化 Q-rear = (QueuePtr)new NOde(); Q-rear-next = Q-rear; Void EnSqlList