湖数据结构试卷(040821)A

湖州师范学院2005—2006学年第一学期《数据结构》期末考试试卷（A）（适用班级040821）学院 班级 学号—姓名 成绩 题号四五总分分数得分|一、单选题（每小题1分，共15分，将正确的答案填入下列表格中）1234567891011121314151．哪一种链表可以从指向任一结点的指针出发访问链表中的每一结点A）带头结点单链表B）不带头结点单链表C）双向链表D）循环链表2． 进行广度优先搜索的算法需利用一个（）A）堆栈B）队列C）数组D）堆栈和队列3．设二叉树如下图，则中序遍历的顺序是（）MGDEBHKFCAD)DGMBEHFKCA4．一个栈的输入序列是1，2，3，4，5，在进栈过程中可以出栈，则栈的不可能输出序列是()A)5，4，3，2，1 B)4，5，3，2，1C)4，3，5，1，2D)1，2，3，4，55．线性表采用顺序存储，其地址()A)必须是连续的B)不必是连续的C)一定不连续 D)以上答案都不对6．深度为5的二叉树最多的结点数为()A)16B)32C)31D)10单链表中，在指针P所指结点后插入一个结点Q,其修改指针的语句是()Q->next=P->next;P->next=Q;P=P->next;P->next:=P->next;Q=P->next;Q->next=P->next;P->next=Q;Q->next=P->next;假定一棵二叉树的结点个数为20,则它的最大高度是( )A)5B)6C)20D)18n个顶点的连通图至少有多少条边()A)nB)n-1C)n(n-1)D)2n栈和队列都是()A)顺序存储的线性表 B)链式存储的线性表C)限制存储的线性表 D)限制存储的非线性结构单循环链表的主要优点是( )。不再需要头指针已知某个结点的位置后，能够容易找到它的直接前趋在进行插入，删除运算时，能更好地保证链表不断开从表中任一结点出发都能扫描到整个链表下列二叉树中，( )可用于实现符号的不等长高效编码。A.哈夫曼树 B.完全二叉树 C.二叉平衡树D.二叉排序树在Hash函数H(k)=kMODm中，一般来讲，m应取( )。A.奇数B.偶数 C.素数D.充分大的数指针p所指的元素是双向循环链表L的尾元素的条件是( )；A)p=L;B)p=NULL;C)p->left=L;D)p->right=L;若队列采用链式存储，则该链队列()A)不存在队空的情况 B)有队满的情况

C）入队前要先判断队满否 D）出队前先要判断队空否星幻二、判断题（每小题1分，共10分）[]线性结构的每个结点可能有唯一的前趋和后继。2．[ ]对于任意给定的图，通过图中的任何结点都可访问图中的所有结点。[ ] 单链表中每个结点都恰好包含一个指针。[]哈夫曼树就是完全二叉树。[ ] 完全二叉树中，若一个结点没有左儿子，则它是树叶。[ ] 由于在线性表的链接存储表示中增加了指针字段，所以它比线性表的顺序表示更浪费空间。[ ] 线性表采用链式存储后，线性表的长度等于链表中的结点个数[ ] 栈只能采用链式存储方式。[ ] 在栈满的情况下不能作进栈运算，否则将产生“上溢”。[ ]二分查找适用于有序表。三、 应用题（每小题6分，共30分）1.试对下图所示的二叉树，写出对其进行前序和后序遍历的顶点序列，并画出后序线索树。2．给出下图的一个拓扑序列并画出它的邻接表。3、设散列函数为H(K)=Kmod7,散列表的地址空间为0〜6,开始时散列表为空，用线性探测法解决冲突，请画出依次插入健值23，14，9,6,30,12,18后的散列表。4、给定记录的键值为{89,67,34,90,11,33,29,83,74},请写出两路归并的过程。5•如果模式串为t=”abcabaa”,则其模式匹配函数next[j](0WjW7)的值分别是多少？四、 算法填空题，在下面程序的空格处填入适当的内容，使其完成指定的功能。(每小题9分，共18分)1.下面过程的功能是：删除带头结点的单链表内所有值为b的结点。其类型定义为：structnode{elemtpdata;structnode*next:;};算法为：voiddelete(structnode*head,elemtpb){structnode*p,*q;p=head;while(p->next!=NuLL)TOC\o"1-5"\h\z{f( ){q=p->next;p->next= ;free(q)；}else ;

用直接插入排序算法进行排序，使数组A递增或不减有序。ins(intA[],intn);{inti,j;TOC\o"1-5"\h\zfor(i= ； ； ){A[0]=A[i];j=i-1；while( ){ A[j+1]=A[j]；j=j-1；}A[j+1]= ；}五、 算法设计题（每小题9分，共27分）1•双向链表的存储结构定义如下：typedefstructDnode{structDnode*prior;{structDnode*prior;/*指向前趋的指针域*/Elemtypedata; /*数据域*/StructDnode*next; /*指向后继的指针域*/}DLinkList;请编写在带表头的双向链表中删除第i个结点的算法（函数）。

2•设计一个算法(用函数voidmoves(sqlist*L)实现)，重排关键字为整数值的n个结点顺序，使所有负值的关键字都排在非负值的关键字之前。intn;设每个结点的数据类型为：之前。intn;#definemaxsize1024typedefintkeytype;typedefstruct{keytypedata[maxsize];/*线性表中结点的实际个数*/}sqlist请写出在中根遍历的线索树中查找后继结点的算法。其结点的类型名为ThreadTnode，结点类型如下情形:LChildLtagdataRtagRChild湖州师范学院2005—2006学年第一学期《数据结构》期末考试试卷（A）参考答案

（适用班级040821）单项选择题（每题1分，共15分）123456789101112131415DBACACACBCDACDD二、判断题（每题1分，共10分）12345678910JXJXJXXXJJ三、应用题（每题6分，共30分）1）前序序列ABDECFG,后序序列DEBGFCA。其后序线索树如下:（注：该线索树中的线索需用笔另勾划出来）3)01234561418239301264)答：89，67，34，90，11，33，29，83，74[89，67][3490][11，33][29，83][74]第一趟[67，89][3490][11，33][29，83][74]第二趟[3467，89，90][11，29，33，83][74]第三趟[1129，33，34，67，83，8990][74]第四趟[11，29，33，34，67，74，83，89，90]5)如果模式串为t=”abcabaa”,则其模式匹配函数next[j](0WjW7)的值分别是多少?解：位置j1234567模式串abcabaanext[j]0111232四、 算法填空题，在下面程序的空格处填入适当的内容，使其完成指定的功能。(每小题9分，共18分)1．p->next->data==b，q->next，p=p->next，2．i=2，i<n，i++，A[0]<A[j]，A[0]五、 算法设计题参考答案(每题9分，共27分)。1.intDLDelete(DLinkList*DL,inti){/*在双向链表DL中删除第i个结点，若成功，则返回1；否则，返回0*/intj=1;DLinkList*temp;temp=DL->next; /*工作指针temp指向被删结点*/while(j<i&&temp!=NULL){ /*在双向链表DL中找第i个结点,*//*使指针temp指向第i个结点*/j++;temp=temp->next;}if(j<i)||temp==NULL)/*第i个结点不存在*/return0;/*删除第i个结点*/temp->prior->next=temp->next;if(temp->next!=NULL)/*表示被删结点不是表尾*/temp->next->prior=temp->prior;free(temp);return1;}2．解：双向扫描：从前向后找一个正数，再从后向前找一个负数，然后交换两者位置。voidmoves(sqlist*L){inti,j;datatypex;i=1;j=L->n;/*线性表中结点的实际个数 ,设数组下标从1开始*/while(i<j){while(L->data[i]<0&&i<j)i++; /*从前向后找正数*/while(L->data[j]>=0&&i<j)j--;/*从后向前找负数*/if(i<j){x=L->data[i];L->data[i]=L->data[j];L->data[j]=x;/*交换*/i++;j--;}}}3．在中根遍历的线索树中查找后继结点的算法对于二叉树中任意结点P，若要找其后继结点，当p-〉Rtag=l时，p-〉Rchild即为p的后继结点；当