资源描述：
《数据结构重修01.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、练习一一、选择题（共15分，每题1.5分）1、适于对动态查找表进行高效率查找的组织结构是（）A．B．分块有序表C．二叉排序树D．线性链表C2、在一个长度为n的线性表中顺序查找值为x的元素时，查找成功时的平均查找长度(即x同元素的平均比较次数，假定查找每个元素的概率都相等)为（）A.nB.n/2C.(n＋1)/2D.(n-1)/2C3、由两个栈共享一个向量空间的好处是：（）A．减少存取时间，降低下溢发生的机率B．节省存储空间，降低上溢发生的机率C．减少存取时间，降低上溢发生的机率D．节省存储空间，降低下溢发生的机率BTKS1CX0114、如下陈述中正确的是（）A．串是一
2、种特殊的线性表B．串的长度必须大于零C．串中元素只能是字母D．空串就是空白串A5、设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主存储,a11为第一个元素,其存储地址为1,每个元素占1个地址空间，则a85的地址为（）A.33B.13C.18D.40A6、在一棵度为3的树中,度为3的结点个数为2,度为2的结点个数为1,则度为0的结点个数为()A．4B．5C．6D．7v1v6v2v3v5v4C7、右图的一个拓扑有序序列为()A.v1v2v3v4v5v6B.v5v1v6v2v3v4C.v1v5v2v3v4v6D.v5v1v6v2v4v3BTKS2CX0128、将长度
3、为n的单链表链接在长度为m的单链表之后的算法的时间复杂度为（）A．○(1)B．○(n)C．○(m)D．○(m+n)C9、用某种排序方法对关键字序列（25，84，21，47，15，27，68，35，20）进行排序时，序列的变化情况如下：20，15，21，25，47，27，68，35，8415，20，21，25，35，27，47，68，8415，20，21，25，27，35，47，68，84则所采用的排序方法是（）A.选择排序B.希尔排序C.归并排序D.快速排序D10、假设一个有n个顶点和e条弧的有向图用邻接表表示,则删除与某个顶点vi相关的所有弧的时间复杂度是()A．○
4、(n)B．○(e)C．○(n+e)D．○(n×e)CTKS3CX013二、判断题（共9分，每题1.5分）（正确的打√，错误的打×）1、（）完全二叉树中，若一个结点没有左孩子，则它必是树叶。√2、（）队列只能采用链式存储方式。×3、（）数据的逻辑结构是指各数据元素之间的逻辑关系，是用户按使用需要而建立的。√4、（）线性表的长度是线性表占用的存储空间的大小。×5、（）所谓冲突即是两个关键字的值相同的元素，其散列地址相同。×6、（）由二叉树的先序序列和中序序列能唯一确定一棵二叉树。√三、填空题（第6题2分，其它每空1分，共15分）1、栈顶的位置是随着____________
5、和___________操作而变化的。入栈出栈TKS4CX0142、在一个带头结点的单循环链表中，p指向尾结点的直接前驱，则指向头结点的指针head可用p表示为head=______________p->next->next3、在一棵高度为5的理想平衡二叉树中，最少含有_______个结点，最多含有_______个结点。16314、数据的逻辑结构是从逻辑关系上描述数据，它与数据的___________无关，是独立于计算机的。存储结构5、在串S=“structure”中，以t为首字符的子串有个。126、取出广义表A=(a,(x,b,c,d))中原子x的函数是______
6、_______________head(head(tail(A)))7、在以HL为表头指针的带表头结点的单链表和循环单链表中，链表为空的条件分别为__________________和________________。HL->next==NULLHL->next==HL8、对于一棵完全二叉树，若一个结点的编号为i，则它的左孩子结点的编号为________，双亲结点的编号为_______。2i[i/2]TKS5CX0159、对于一个具有n个顶点和e条边的有向图和无向图，在其对应的邻接表中，所含边结点分别为_______和_______条。2ee四、应用题（共45分）1、
7、假定用于通信的电文仅由8个字母c1,c2,c3,c4,c5,c6,c7,c8组成,各字母在电文中出现的频率分别为5,25,3,6,10,11,36,4。试为这8个字母设计Huffman编码,使电文中字符的二进制内部表示最短。要求：(1)画出对应的哈夫曼树；(2)各字符的编码表；(3)以各字符出现的频度为权，计算其带权路径的长度。(9分)01001000000101001011110001c1c2c3c4c5c6c7c8(1)哈夫曼树(2)各字符的编码表(3)带权路径的长度wpl=(3+4+5+6)*4+(10+11)*3+(25+36)*2=72+6
