X南大学2010-2011数据结构期末试卷

1、X南大学2010-2011学年度第1学期试卷科目：数据结构试题 B姓名： 学 号： 学院： 专业班级： 成绩登记表（由阅卷教师用红色笔填写）大题号一二三四五总分得分 阅卷教师： 201 年 月 日得分评卷人 一、选择题（共30分，每小题2分）1.在一个长度为n的单链表的第i（0=inext=NULL C. head-next=head D. head!=NULL4.若某线性表最常用的操作是在最后一个元素之后插入一个元素和删除进入表中的最后一个元素，则采用（ ）存储方式最节省运算时间和存储空间。A.单链表 B.仅有头指针的单循环链表C.双向链表 D.有头尾指针的单循环链表5.设有一个顺序栈S，元

2、素a b c d e f依次进栈，如果6个元素出栈的顺序是b d c f e a，则栈的容量至少应该是（）A.2 B.3 C.5 D.66向一个栈顶指针为top的带头结点的非空的链栈中删除结点，则其操作步骤是（）A.top-next=s; B.s-next=top-next;top-next=s; free(s)C. s = top;top= top-next;free(s) D. s = top-next;top= top-next;free(s)7. 以下为平衡二叉排序树的查找算法, 假设表长为N，则算法的时间复杂度为（ ）A）O（1） B） O（N） C） O（N*N） D） O（log

3、2 N）bitree *search_fsortree(t, key)bitree *t;keytype key; while(t!=NULL) if(t-data=key)return(t);if(t-datakey)t=t-lchild;else t=t-rchild;return(NULL);/* SEARCH_FSORTTREE */8. 在解决计算机主机与打印机间速度不匹配问题时通常设置一个打印数据缓冲区，主机将要输出的数据依次写入该缓冲区，而打印机则从该缓冲区中取出数据打印。该缓冲区应该是一个（）结构A、数组B、线性表C、堆栈D、队列9. 一棵有124个叶结点的完全二叉树，最多有（

4、 ）个结点A、247B、248C、249D、25110.一棵非空的二叉树的前序遍历序列和后序遍历序列正好相同，则该二叉树一定满足（）A.所有的结点均无左孩子 B.所有的结点均无右孩子C.只有一个孤立的结点 D.是任意一棵二叉树11. 已知字符A、B、C、D的使用频率（权值）分别为22，7，9，27。对其进行HUFFMAN编码，各字符对应的编码为（ ）A） A（001）B（100）C（110） D（0）B） A（100） B（101）C（0） D（11）C） A（11） B（100）C（111） D（0）D） A（100）B（1011）C（11） D（0）12.在具有N个顶点和N条边的无向图的邻

5、接表存储中，邻接表中结点的总数为（ ）A.N B.2N C.3N D.4N13. 由同一关键字集合构造的各棵二叉排序树( )A. 其形态不一定相同，但平均查找长度相同B. 其形态不一定相同，平均查找长度也不一定相同C. 其形态均相同，但平均查找长度不一定相同D. 其形态均相同，平均查找长度也都相同D.以上都不是14.设有1000个基本有序的元素，希望用最快的速度挑选出其中前10个最大的元素，最后选用（）排序法。A.冒泡排序 B.快速排序 C. 直接插入排序 D. 归并排序15.对序列（15，9，7，8，20，-1，4）进行排序，进行一趟排序后，数据的排列变为（4，9，7，8，-1，15，20）

6、，则采用的是（）排序。A.选择排序 B.快速排序 C.希尔排序 D.冒泡排序得分评卷人二、填空题（20分，每空2分）16.栈的逻辑特点是_，队列的逻辑特点是 _。17、将含100个结点的完全二叉树从根开始，每层从左到右依次对结点编号，根结点的编号为1，则编号为31的结点的双亲的编号为_，其右子的编号为_。18、设树F由T1，T2,T3三棵子树组成，与F对应的二叉树为B。已知T1,T2,T3的结点数分别为x，y，z，则该二叉树B的左子树中有_个结点，右子树中有_个结点。（x-1,y+z）19、设链队列的队头指针为front，队尾指针为rear，队列为空的条件是_，队列为满的条件是_。20. 在有

7、向图中，以顶点v为终点的边的数目称为v的_。21. 堆是一个键值序列 (k1,k2,kn)，对i=1,2, ，满足_。（kik2i且kik2i+1 (2i+1n)）得分评卷人三、应用题（共25分）22对下图所示的树，分别写出其先序和后序序列，并转换成对应的二叉树。（5分）先序：A B E C F G D H KI J后序：E B F G C K H I J D A 23.对下面给定的图用克鲁斯卡尔算法（从顶点2开始）求最小生成树，要求画出最小生成树，并按构造过程给出边的序列。（5分）（见图1）克鲁斯卡尔算法：（0，2），（3，5），（1，4），（2，5），（1，2）普利姆算法： （2，0），（

8、2，5），（5，3），（2，1），（1，4）图1 24.设给定的排序码序列为（72，73，71，23，94，16，05，68），请写出快速排序过程中每趟排序的结果。（5分）68 05 71 23 167294 73 16 05 2368 71 7294 7305162368 71 7294 73 05 16 23 68 71 72 73 9425.假定一个待存储的线性表为 22,41,53,46,30,13,1,67 ,散列地址空间为HT8，散列函数为H（k）=key%8,若采用线性探查法处理冲突，请计算每个元素的散列地址（5分）。画出最后得到的散列表（2分），并求出平均查找长度（3分）。（共

9、10分）0 1 2 3 4 5 6 7 8 比较次数 3 1 6 3 2 1 1 2224153463013167 平均查找长度ASL=1/8* (3+1+6+3+2+1+1+2)=19/8 得分评卷人四、算法测试（分）26. 代码如下：（6分）下面是在递增有序表Rn中的下标在low到high范围内的区域查找键值为K的元素的二分查找的递归算法，请在划线处填上适当的内容。/* 有序表R进行二分查找递归算法 */ int halfsearch（R, low, high, k） int low, high ,k; /* 在顺序表R上进行二分查找, k为给定的关键字值 */ int; rectype

10、R; int mid; if （lowhigh） _ ; /* 检索失败 */ else mid=(high+low)/2; /* 设置查找的中间位置mid */ switch（k） case Rmid.keyk: return（halfsearch（R, _）; break; case Rmid.key=k: return（mid）; break; /* SWITCH */ /* ELSE */ /* HALFSEARCH */ 见书上第318页：0；mid+1,hiht,k; low,mid-1,k27、设h是带表头结点的单链表的头指针，请设计一个逆置这个单链表的程序。即原链表为(a1,a

11、2,a3an)，逆置后变为( an,an-1a2,a1)。（6分）单链表结点结构为：typedef struct node int data; _ *link LNode; （2分） （ struct node ）void invert(LNode *h) LNode *s,*p; p=h-link; h-link=_;（2分） （0） （ h-next=NULL） while(p!=NULL) s=p; p=p-link; _（2分） （S-next=H-next;） h-link=s;10得分评卷人五、编写算法（1分）28、试编写算法，在一个循环单链表中删除结点S，且要求函数返回该链表的一

12、个入口指针。 假设表长大于1，且表中即无头结点，也无头指针，函数原型为void delete_xyz(NODE*S)。（分）解一：void delete xyz(NODE *S) NODE *f;f=s.next;while(f.next!=s);/找到S点的前一结点f=f.next;f.next=s.next;free(s);解二：解一的问题是删除结点s后，没有再指向链表的指针了。NODE *delete xyz(NODE *S) NODE *f;f=s.next;while(f.next!=s);f=f.next;f.next=s.next;free(s);return f ;29、已知某

13、二叉树BINTREE的结点结构如下,根结点的指针为T，试编写一算法，求该二叉树的深度。(分) Lchild Data Rchild 函数形式（参考）： void BiTreeDepth(BiTree T, int level, int &depth)算法1：用前序遍历的递归算法实现。int level=1;int depth=0;void BiTreeDepth(BiTree T, int level, int &depth) /T指向二叉树的根，level为T所指结点所在层次， /其初值为1，depth为当前求得的最大层次,其初值为0 if (T) if (leveldepth) depth

14、=level; BiTreeDepth(T-Lchild, level+1, depth); BiTreeDepth(T-Rchild, level+1, depth); /if/BiTreeDepth算法2： 算法思路：用递归实现该算法。如果二叉树为空，则返回 0；如果二叉树只有一个结点（根结点），返回 1，否则返回根结点的左分支的深度与右分支的深度中较大者加 1。 算法实现如下： int GetHeight(BINTREE T) int lh; int rh; if (T = null) return 0; else if (T.LChild = null & T.RChild = nul

15、l) return 1; else lh = GetHeight(T.LChild); rh = GetHeight(T.RChild); return (lhrh?lh:rh) + 1; 算法3：非递归算法(按层遍历)，用队列实现。（参阅P187例6.4）void leveltraverse(Bitreenode *T,int &level) Bitreenode *p; Queue Q; /队列Q定义的结点结构包含两个域：Q.LINK和Q.level. 其中 Q.LINK（Bitreenode型）记录入队的结点的指针 地址，Q.level（int型）记录该结点的深度 initqueue(Q); /初始化队列 p=T; Enqueue(Q, p，1); /根结点入队，