资源预览内容
第1页 / 共8页
第2页 / 共8页
第3页 / 共8页
第4页 / 共8页
第5页 / 共8页
第6页 / 共8页
第7页 / 共8页
第8页 / 共8页
亲,该文档总共8页全部预览完了,如果喜欢就下载吧!
资源描述
数据结构(本)试题 D 第 1 页(共 8 页) 数据结构2008 年 3 月一、单项选择题(每小题一、单项选择题(每小题 2 分,共分,共 30 分)分)1非空的单向循环链表的尾结点满足( ) (设头指针为 head,指针 p 指向尾结点) 。Ap-next = =NULL Bp= =NULL Cp-next= =head Dp= =head 2一种逻辑结构( ) 。A可以有不同的存储结构 B只能有唯一的存储结构 C是指某一种数据元素之间的存储关系 D以上三种说法均不正确 3把数据存储到计算机中,并具体体现数据元素间的逻辑结构称为( ) 。A物理结构 B逻辑结构 C算法的具体实现 D给相关变量分配存储单元 4在一个单链表中 p 所指结点之后插入一个 s 所指的结点时,可执行( ) 。Ap-next= s; s-next= p-next Bp-next=s-next; Cp=s-next Ds-next=p-next; p-next=s; 5在一个链队中,假设 f 和 r 分别为队头和队尾指针,则插入 s 所指结点的运算为( ) 。Af-next=s; f=s; Br-next=s;r=s; Cs-next=r;r=s; Ds-next=f;f=s; 6元素 1,3,5,7 按顺序依次进栈,则该栈的不可能输出序列是( ) (进栈出栈可 以交替进行) 。A7,5,3,1 B1,3,5,7 C7,5,1,3 D3,1,7,5 7设有一个 20 阶的对称矩阵 A,采用压缩存储的方式,将其下三角部分以行序为主序 存储到一维数组 B 中(数组下标从 1 开始) ,则矩阵中元素 a9,2在一维数组 B 中的下标是( ) 。 A41 B32 C18 D38 8设有两个串 p 和 q,求 q 在 p 中首次出现的位置的运算称作( ) 。A连接 B求子串 C求串长 D模式匹配 9在一棵二叉树中,若编号为 i 的结点存在左孩子,则左孩子的顺序编号为( ) 。A2i B2i-1 C2i+1 D2i+2 10设一棵有 n 个叶结点的二叉树,除叶结点外每个结点度数都为 2,则该树共有( )个结点。 A2n B2n+1 C2n+2 D2n-1题号一二三四总分分数得分评卷人数据结构(本)试题 D 第 2 页(共 8 页) 11已知如图 1 所示的一个图,若从顶点 a 出发,按深度优先搜索法进行遍历,则可能 得到的一种顶点序列为( ) 。Aabecdf Bacfebd Caebcfd Daedfcb 图 1 12线性表以( )方式存储,能进行折半查找。A关键字有序的顺序 B顺序 C链接 D二插树 13有一个长度为 12 的有序表,按折半查找对该表进行查找,在等概率情况下查找成 功的平均比较次数为( ) 。 A35/12 B39/12 C41/12 D37/12 14设已有 m 个元素有序,在未排好序的序列中挑选第 m+1 个元素,并且只经过一次元 素的交换就使第 m+1 个元素排序到位,该方法是( ) 。A折半排序 B冒泡排序 C归并排序 D简单选择排序 15一组记录的关键字序列为(47,80,57,39,41,46) ,利用堆排序(堆顶元素是 最小元素)的方法建立的初始堆为( ) 。A39,41,46,80,47,57 B39,47,46,80,41,57 C41,39,46,47,57,80 D39,80,46,47,41,57二、填空题(每小题二、填空题(每小题 2 分,共分,共 24 分)分)1结构中的数据元素存在一对多的关系称为_结构。 2求两个 n 阶矩阵的乘积,算法的基本操作和时间复杂度分别为_和 _。 3在一个单向链表中,要删除 p 所指结点,已知 q 指向 p 所指结点的前驱结点。则可 以用操作_ _。 4向一个栈顶指针为 h 的链栈中插入一个 s 所指结点时,可执行_ _和 h=s; 操作。(结点的指针域为 next) 5串的两种最基本的存储方式分别是_ _ _和 _ _。 6对稀疏矩阵进行压缩存储,矩阵中每个非零元素对应的三元组包括该元素的 _、_和_ _三项信息。 7设有一棵深度为 4 的完全二叉树,第四层上有 5 个结点,该树共有_个结点。 (根所在结点为第 1 层) 8一棵二叉树中有 2n-2 条边(结点间的连线) ,其中每一个非叶结点的度数都为 2, 则该树共有_个非叶结点。得分评卷人bdfeca数据结构(本)试题 D 第 3 页(共 8 页) 9如图 2 所示的二叉树,其中序遍历序列为_ _。图 210哈希函数是记录关键字值与该记录_ _之间所构造的对应关系。 11在对一组记录(55,39,97,22,16,73,65,47,88)进行直接插入排序时,当把第 7 个记录 65 插入到有序表时,为寻找插入位置需比较_次。 12n 个元素进行冒泡法排序,通常需要进行_ _趟冒泡,第 j 趟冒泡要进行_ _次元素间的比较。三、综合题(每小题三、综合题(每小题 1010 分,共分,共 3030 分)分)1设查找表为(7,15,21,22,40,58,68,80,88,89,120) ,元素的下标依次为 1,2,3,,11.(1)画出对上述查找表进行折半查找所对应的判定树(树中结点用下标表示) (2)说明成功查找到元素 40 需要经过多少次比较? (3)求在等概率条件下,成功查找的平均比较次数?得 分评卷人efg ibachd数据结构(本)试题 D 第 4 页(共 8 页) 2 (1)如果二叉树中任一结点的值均大于其左孩子的值、小于其右孩子的值,则该树为二 叉排序树,这种说法是否正确?若认为正确,则回答正确,若认为不正确,则举例说明。(2)设有数据集合40,29,7,73,101,4,55,2,81,92,39,依次取集合中各数 据,构造一棵二叉排序树。3(1)以 2,3,4,7,8,9 作为叶结点的权,构造一棵哈夫曼树,给出相应权重值叶结点 的哈夫曼编码。 (2) 一棵哈夫曼树有 n 个叶结点,它一共有多少个结点?简述理由?数据结构(本)试题 D 第 5 页(共 8 页) 四、程序填空题(每空四、程序填空题(每空 2 2 分,共分,共 1616 分)分)1设线性表为(6,10,16,4) ,以下程序用说明结构变量的方法建立单向链表,并输 出链表中各结点中的数据。#define NULL 0void main( )NODE a,b,c,d,*head,*p; a.data=6; b.data=10; c.data=16; d.data=4; /*d 是尾结点*/ head= (1) ; a.next= b.next= c.next=(2) ; /*以上结束建表过程*/ p=head; /*p 为工作指针,准备输出链表*/ doprintf(“%dn”, (3) );(4) ;while( (5) ); 2以下程序是中序遍历二叉树的递归算法的程序,完成程序中空格部分(树结构中左、 右指针域分别为 left 和 right,数据域 data 为字符型,BT 指向根结点) 。 void Inorder (struct BTreeNode *BT) if(BT!=NULL)(1) ;(2) ;Inorder(BT-right); 得分评卷人efabcd数据结构(本)试题 D 第 6 页(共 8 页) 利用上述程序对右图进行遍历,结果是 (3) ;图 3答案及评分标准(供参考) 一、单项选择题(每小题一、单项选择题(每小题 2 分,共分,共 30 分)分) 1C 2A 3A 4D 5B 6C 7D 8D 9A 10D 11D 12A 13D 14D 15A 二、填空题(每小题二、填空题(每小题 2 分,共分,共 24 分)分) 1树形 2乘法,O(n3) 3q-next=p-next; 4s-next=h; 5顺序存储 链式存储 6行下标、列下标、非零元素值 712 8n-1 9dgbaechif 10存储地址 113 12n-1,n-j三、综合题(每小题三、综合题(每小题 1010 分,共分,共 3030 分)分) 1 (1)图 4(2)4 次 (3)ASL=(1+2*2+3*4+4*4)/11=34711852101396数据结构(本)试题 D 第 7 页(共 8 页) 2(1)不正确,例图 5(2)图 63(1)图 715423955928141017240732997589243331518数据结构(本)试题 D 第 8 页(共 8 页) 2:0000 30001 4001 710 811 901 (2)2n-1 个,因为非叶结点数比叶结点数少一个。四、程序填空题(每空四、程序填空题(每空 2 2 分,共分,共 1616 分)分) 1 (1)&a (2)d-next=NULL (3)p-data (4)p=p-next (5)p!=NULL2 (1)Inorder(BT-left) (2) printf(“%c”,BT-data) (3)dbeafc
网站客服QQ:2055934822
金锄头文库版权所有
经营许可证:蜀ICP备13022795号 | 川公网安备 51140202000112号