2008级数据结构考试试卷(a).doc

数据结构考试试卷（A） 班级：_________学号__________姓名___________ （注意：试卷满分100，时间100分钟，请考生将答案做于试卷答题纸上，违者零分论处） 填空题（每个空格1分，共20分,错填或不填均无分） 数据结构通常有四种基本的结构，分别是：（ ）、（ ）、（ ）、（ ）。 数据元素在计算机中的两种不同的存储结构：（ ）和（ ）。 在线性结构中，开始结点（ ）前驱结点，其余每个结点有且只有（ ）前驱结点。 设有一个空栈，现输入序列为E，D，C，B，A，经过push，push，pop，push，pop，push，pop后，栈顶元素是（ ）。 在队列中入队操作由（ ）指针进行控制，出队操作由（ ）指针进行控制。 一维数组的元素起始地址LOC[6]=1000，元素长度为4，LOC[3]的起始地址为（）。 广义表 ( ( a, b ),c , d , ( e,f ) ) 的表尾是（ ）。 具有m个叶结点的哈夫曼树共有（ ）个结点。 强连通分量是（ ）图的极大连通子图。 n个结点的无向图的边数最多有（ ）条。 用迪杰斯特拉算法求某一顶点到其余各顶点间的最短路径是按照路径长度（ ）次序来得到最短路径。 希尔排序属于（ ）排序，快速排序属于（ ）排序，堆排序属于（ ）排序。 单项选择题（共15小题，每小题2分，共30分） 1、在（ ）运算中，使用顺序表比链表好。 A、插入 B、根据序号查找 C、删除 D、根据元素值查找 2、在一个单链表中，已知*q结点是*p结点的前驱结点，若在*q和*p之间插入结点*s，则执行（ ）。 A、s-next=p-next;p-next=s; B、p-next=s-next;s-next=p; C、q-next=s;s-next=p; D、p-next=s;s-next=q; 3、设有一顺序栈S，元素s1,s2,s3,s4,s5,s6依次入栈，如果6个元素的先后出栈顺序是s2,s3,s4,s6,s5,s1，则栈的容量至少应该是（ ）。 A、2 B、3 C、5 D、6 4、以下结论正确的是（ ）。 空串和空格串是相同的 B、“TEL”是“telephone”的子串 C、空串是0个字符的串 D、空串长度为1 5、稀疏矩阵的一般的压缩方法有（ ）。 A、二维数组 B、广义表 C、三元组表 D、一维数组 6、深度为5的二叉树至多有（ ）个结点。 A、16 B、31 C、15 D、30 7、将一颗有100个结点的完全二叉树从上往下，从左往右依次对结点进行编号，根结点的编号为1，则编号为49的结点的右孩子编号为（ ）。 A、98 B、99 C、49 D、50 8、最短路径算法可用（ ）实现。 A、普里姆算法 B、迪杰斯特拉算法 C、哈夫曼算法 D、哈希算法 9、通常把查找过程中对关键字需要执行的（ ）作为衡量一个查找算法效率优劣的标准。 A、BST B、WPL C、ASL D、BFS 10、设有10000个无序的元素，希望以最快的速度挑选出其中前10个最大的元素，最好选用的排序方法是（ ）。 A、堆排序 B、起泡排序 C、快速排序 D、基数排序 11、计算机算法必须具备输入输出和（） A、计算方法 B、排序方法 C、解决问题的有限运算步骤 D、程序设计方法 12、树最适合用来表示（） A、有序数据元素 B、无序数据元素 C、现有元素之间具有分支层次关系的数据 D、元素之间无联系的数据 13、完全二叉树（）二叉树 A、一定是满 B、可能是满 C、不是 D、一定不是 14、下列说法正确的是：（） 哈希表是解决排序的方法 图的结点关系是任意的，在拓扑排序中，弧头结点可能会出现在弧尾结点之前 图的广度优先有哪些信誉好的足球投注网站算法中采用了递归 树是图的一种特殊形式 15、由普通树转换成二叉树是非空的二叉树，则转换后的二叉树（） A、根结点无右子树 B、根结点无左子树的二叉树 C、根结点可能有左右子树 D、各结点只有一个儿子的二叉树 三、解答题（本大题共5小题，每题6分，共30分）： 将图中的森林转换成与之对应的一棵二叉树。（6分） 某密码电文由8个字母组成，每个字母在电文中出现的频率分别是：{7、19、2、6、32、3、21、10}，将这8个字母设计相应的哈夫曼树，并写出其编码。（6分） 所示为无向连通网，要求用普里姆（Prim）算法构造出它的最小生成树。（6分） 写出有向图中三种不同的拓扑排序序列。（6分） 对下列一组关键字{46、58、15、45、90、18、10、62}按非递减序进行快速排序，试写