计算机九九级第四学期数据结构试题934.doc

计算机九九级第四学期数据结构试题934 14、书犹药也，善读之可以医愚——刘向 《数据结构》模拟题八 题号 一 二 三 四 五 六 总分 分数 得分 评卷人 一、 单选题（每小题2分，共8分） 1、 在一个长度为n的顺序线性表中顺序查找值为x的元素时，查找成功时的平均查找长度（即x与元素的平均比较次数，假定查找每个元素的概率都相等）为 ( ) A n B n/2 C (n+1)/2 D (n-1)/2 2、 在一个单链表中,若q所指结点是p所指结点的前驱结点,若在q与p之间插入一个s所指的结点,则执行( ) A s→link=p→link; p→link=s; B p→link=s; s→link=q; C p→link=s→link; s→link=p; D q →link=s; s→link =p; 3、 栈的插入和删除操作在（ ）进行 　　　A 栈顶 B 栈底 C 任意位置 D 指定位置 4、 由权值分别为11，8，6，2，5的叶子结点生成一棵哈夫曼树，它的带权路径长度为（ ） A 24 B 71 C 48 D 53 得分 评卷人 二、 填空题（每空1分，共32分） 1、 数据的逻辑结构被分为__________、 ___________ 、________和________四种 2、 一种抽象数据类型包括______________和_____________两个部分 3、 在下面的数组a中链接存储着一个线性表，表头指针为a[o].next，则该线性表为_________________________________________________ a 0 1 2 3 4 5 6 7 8 60 56 42 38 74 25 4 3 7 6 2 0 1 data next 4、 在以HL为表头指针的带表头附加结点的单链表和循环单链表中，判断链表为空的条件分别为________________和____________________ 5、 用具有n个元素的一维数组存储一个循环队列，则其队首指针总是指向队首元素的___________，该循环队列的最大长度为__________ 6、 当堆栈采用顺序存储结构时，栈顶元素的值可用-------表示；当堆栈采用链接存储结构时，栈顶元素的值可用_______________表示 7、 一棵高度为5的二叉树中最少含有_________个结点，最多含有________个结点； 一棵高度为5的理想平衡树中，最少含有_________个结点，最多含有_________个结点 8、 在图的邻接表中，每个结点被称为____________，通常它包含三个域：一是_____________；二是___________；三是_____________ 9、 在一个索引文件的索引表中，每个索引项包含对应记录的_________和___________两项数据 10、 假定一棵树的广义表表示为A（B（C，D（E，F，G），H（I，J））），则树中所含的结点数为_________个，树的深度为_________,树的度为________, 结点H的双亲结点为________,孩子结点为_______________ 11、 在堆排序的过程中，对任一分支结点进行筛运算的时间复杂度为_________,整个堆排序过程的时间复杂度为________________ 12、 在对m阶的B_树插入元素的过程中，每向一个结点插入一个索引项（叶子结点中的索引项为关键字和空指针）后，若该结点的索引项数等于______个，则必须把它分裂为_______个结点 得分 评卷人 三、 运算题（每小题6分，共24分） 1、 已知一组记录的排序码为（46，79，56，38，40，80, 95，24），写出对其进行快速排序的每一次划分结果 2、 一个线性表为B=（12，23，45，57，20，03，78，31，15，36），设散列表为HT[0..12]，散列函数为H（key）= key % 13并用线性探查法解决冲突，请画出散列表，并计算等概率