聊城大学《数据结构》练习题及参考答案

《数据结构》练习题一、单选题1.下列关于无向连通图特性的叙述中，正确的是()。=1\*ROMANI.所有顶点的度之和为偶数 =2\*ROMANII.边数大于顶点个数减1 =3\*ROMANIII.至少有一个顶点的度为1A.只有=1\*ROMANI B.只有=2\*ROMANII C.=1\*ROMANI和=2\*ROMANII D.=1\*ROMANI和=3\*ROMANIII2.一个具有n个顶点的无向图，最多包含____条边。A.n(n-1) B.n(n+1) C.n(n+1)/2 D.n(n-1)/23.有关二叉树下列说法正确的是()。A．二叉树的度为2 B．一棵二叉树的度可以小于2 C．二叉树中至少有一个结点的度为2 D．二叉树中任何一个结点的度都为24.折半查找有序表(6,15,30,37,65,68,70,72,89,99),若查找元素37,需依次与表中元素____进行比较,。A.65,15,37B.68,30,37C.65,15,30D.65,15,30,375.在表长为n的顺序表上做插入运算，平均要移动的结点数为()。A.nB.n/2C.n/3D.n/46.____又称为FIFO表。A.队列B.散列表C.栈D.哈希表7.在单链表中，已知p,q,s是指向结点的指针，且q是p的直接前驱，若在q和p之间插入s，则需执行_____。A.s->next=p->next;p->next=s B.q->next=s;s->next=p;C.p->next=s->next;s->next=p D.p->next=s;s->next=q;8.以下数据结构中，（）是非线性数据结构。A.树B.字符串C.队D.栈9..若一个栈的输入序列为1,2,3,…,n，输出序列的第一个元素是i，则第j个输出元素是____。A.i-j-1B.i-jC.j-i+1D.不确定的10.对任何一棵二叉树T，如果其终端结点数为n0，度为2的结点树为n2，则()。A.n2=2n0+1B.n2=n0+1C.n0=2n0+1D.n0=n2+111.有n(n>0)个结点的完全二叉树的深度是____。A.log2(n)+1B.log2(n)C.log2(n+1)D.log2(n)+112.一个对象序列的排序码为{46,79,56,38,40,84}，采用快速排序（以位于最左位置的对象为基准）所得到的第一次划分结果为()。A.{38,46,79,56,40,84} B.{38,79,56,46,40,84} C.{40,38,46,56,79,84} D.{38,46,56,79,40,84}二、算法分析与设计题1.假设通信电文使用的字符集为{a,b,c,d,e,f}，各字符在电文中出现的频度分别为：34，5，12，23，8，18，试为这6个字符设计哈夫曼编码。要求画出所构造的哈夫曼树，计算树的带权路径长度，分别写出每个字符对应的编码。2.试写一个算法，识别依次读入的一个以#为结束符的字符序列是否为形如‘序列1&序列2’模式的字符序列。其中序列1和序列2中都不含字符‘&’，且序列2是序列1的逆序列。例如，‘a+b&b+a’是该模式的字符序列，而‘1+3&3-1’则不是。要求：（1）描述算法的基本设计思想；（2）根据设计思想，采用类C语言描述算法，关键处请给出简要解释。三、应用题1.如下图所示二叉树，在访问二叉树结点时按所标示的数字顺序访问每个结点，写出遍历算法。2.已知一组关键字为{21,13,16,43,35,11,18}，采用哈希函数H(k)=kmod7，并用线性探测再散列法处理冲突，要求：(1)在[0…7]的地址空间上构造哈希表；散列地址01234567关键字(2)求等概率下查找成功的平均查找长度ASL；(3)求装填因子а。3.已知长度为n的线性表A采用顺序存储结构，并且元素按值大小非递减排列，下面的算法删除线性表中多余的值相同的元素。例如：(7，10，10，21，30，42，42，42，51，70)，经算法操作后变为(7，10，21，30，42，51，70),请在算法的空白处填入适当内容，使之能够正常工作。voidalgorithm(intA[N],intn){i=1while________________if(A[i]≠A[i+1])i++;//查找满足条件的元素else//删除满足条件的元素{for________________A[j-1]=A[j];

______________//修改线性表的长度}//else}//algorithm4.已知权值序列R={2，4，6，8，10}(1)构造一棵哈夫曼树；(2)计算出树的带权路径长度WPL。参考答案一、单选题ADBDBABADDAC算法分析与设计题1.假设通信电文使用的字符集为{a,b,c,d,e,f}，各字符在电文中出现的频度分别为：34，5，12，23，8，18，试为这6个字符设计哈夫曼编码。要求画出所构造的哈夫曼树，计算树的带权路径长度，分别写出每个字符对应的编码。10059100594125341823131258WPL=5×4＋8×4＋12×3＋34×2＋18×2＋23×2＝238字符集的哈夫曼编码分别为：01，0000，001，11，0001，10。2.试写一个算法，识别依次读入的一个以#为结束符的字符序列是否为形如‘序列1&序列2’模式的字符序列。其中序列1和序列2中都不含字符‘&’，且序列2是序列1的逆序列。例如，‘a+b&b+a’是该模式的字符序列，而‘1+3&3-1’则不是。要求：（1）描述算法的基本设计思想；（2）根据设计思想，采用类C语言描述算法，关键处请给出简要解释。(1)可利用栈的先进后出性质来解决此问题，字符‘&’前面的字符都入栈，对于字符‘&’后面的字符序列，判断是否与出栈元素相等，如果一直到输入字符’#’全部相等，并且最后的栈为空栈，则是符合要求的序列，所有其它情况都是不符合要求的序列（2）StatusIsReverse(){InitStack(s); while((e=getchar())!='&')push(s,e); while((e=getchar())!='#'){if(StackEmpty(s))returnERROR;pop(s,c);if(e!=c)returnERROR;}if(!StackEmpty(s))returnERROR;returnOK; }//IsReverse三、应用题1.如下图所示二叉树，在访问二叉树结点时按所标示的数字顺序访问每个结点，写出遍历算法。voidLayerOrder(BiTreeT)// {

if(T)

{

InitQueue(Q);//建立工作队列

p=T;

EnQueue(Q,p);//根结点入队

while(!QueueEmpty(Q))

{

DeQueue(Q,p);

Visit(p->data);

if(p->lchild)

EnQueue(Q,p->lchild);

if(p->rchild)

EnQueue(Q,p->rchild);

}

}

} 2.已知一组关键字为{21,13,16,43,35,11,18}，采用哈希函数H(k)=kmod7，并用线性探测再散列法处理冲突，要求：(1)在[0…7]的地址空间上构造哈希表；解：散列地址01234567关键字21431635111813(2)求等概率下查找成功的平均查找长度ASL；解：(3)求装填因子а。解：а=3.已知长度为n的线性表A采用顺序存储结构，并且元素按值大小非递减排列，下面的算法删除线性表中多余的值相同的元素。例如：(7，10，10，21，30，42，42，42，51，70)，经算法操作后变为(7，10，21，30，42，51，70),请在算法的空白处填入适当内容，使之能够正常工作。voidalgorithm(intA[N],intn){i=1while_____（i<=n）______if(A[i]≠A[i+1])i++;//查找满足条件的元素else