《2011年韩山师范学院本科插班生《数据结构》试卷(共6页).doc》由会员分享，可在线阅读，更多相关《2011年韩山师范学院本科插班生《数据结构》试卷(共6页).doc（6页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、精选优质文档-倾情为你奉上2011年韩山师范学院本科插班生考试试卷计算机科学与技术 专业 数据结构一、单项选择题（每题2分，共40分）1、在一个长度为n的顺序存储的线性表中，向第i个元素（1in+1）之前插入一个新元素时，需要向后依次移 个元素。A. n- i B. n- i +1 C. n- i -1 D. i2、若进栈序列为1、2、3、4；进栈过程中可以出栈，则 是不可能的出栈序列。A.3、4、2、1 B.2、4、3、1 C.1、4、2、3 D.3、2、1、43、在一个具有n个结点的有序单链表中插入一个新结点并仍然有序的时间复杂性为 。A.O(1) B.O(n) C.O(n2) D.O(l
2、og2n)4、从一个具有n个结点的单链表中查找其值等于X结点时，在查找成功的情况下，需平均比较 个结点。A.n B.n/2 C.（n-1）/2 D.（n+1）/25、一个中缀算术表达式为5 +（7 - X） * Y，则对应的后缀算术表达式为 。A.5 7 - + X Y * B.5 7 X + - Y *C.5 7 X - + Y * D.5 7 X Y - + *6、在一棵度为3的树中，度为3的结点数为2个，度为2的结点数为1个，度为1的结点数为2 个，那么度为0的结点数为 个。A.4 B.5 C.6 D.77、在存储数据时，通常不仅要存储各数据元素的值，而且还要存储 。A.数据的处理方法B
3、.数据元素之间的关系C.数据元素的类型 D.数据的存储方法8、在一棵二叉树中第五层上的结点数最多为 。A.8 B.15 C.16 D.329、在一棵完全二叉树中，若编号为i的结点有右子女，则该结点的编号为 。A.2i-1 B.2i+1 C.2i-1 D.i/210、由权值分别为16,12,19,16,28的叶子结点生成一棵哈夫曼树，它的带权路径长度为 。A.91 B.126 C.148 D.21011、以知8个数据元素为（34，76，45，18，26，54，92，65），按照依次插入结点的方法生成一棵二叉排序树，则该树的深度为 。A.4 B.5 C.6 D.712、在一个图中，所有顶点的度数之
4、和等于所有边数的 倍。A.1/2 B.1 C.2 D.413、用二分法查找一个长度为10的、排好序的线性表，查找不成功时，最多需要比较 次。A.5 B.2 C.4 D.114、设散列(Hash)函数为H(K)=K MOD 7,一组关键码为（23,14,9,6,30,12，18），散列表T的地址空间为0.6。用线性探测法解决冲突，依次将这组关键码插入T中，得到的散列表为 。A. 0 1 2 3 4 5 6 14 6 23 9 18 30 12 B.0 1 2 3 4 5 614 18 23 9 30 12 6C.0 1 2 3 4 5 6 14 12 9 23 30 18 6 D.0 1 2 3
5、 4 5 6 14 23 30 14 18 12 915、如果一棵二叉树中任何一个结点的值都小于它的左子树上所有结点的值而大于它的右树上所有结点的值，要得到这棵二叉树中各结点值的递减序列，应按 次序排列结点？A. 先序 B. 中序 C. 后序 D. 按层16、在一个具有N个顶点的无向完全图中，包含有 条边。A.n（n-1）/2 B.n（n-1） C.n（n+1）/2 D.n217、在一个3阶的B 树上，每个结点所含的子树数目最多为 ，最少为 。A. 1，3 B. 2，1 C. 3，2 D. 4，418、采用二分查找的方法查找长度为n的有序表时，查找每个元素时平均比较次数 对应的判定树的高度（假
6、定高度大于等于2）。A.小于 B. 大于 C. 等于 D. 大于等于19、一组记录的排序码为（25，48，16，35，79，82，23，40，36，72），其中含有5个长度为2的有序表，按归并排序方法对该序列进行一趟归并后的结果为 。A. （16，25，35，48，23，40，79，82，36，72）B. （16，25，35，48，79，82，23，36，40，72）C. （16，25，48，35，79，82，23，36，40，72）D. （16，25，35，48，23，40，36，72，79，82）20、一组记录的排序码为（46，79，56，38，40，84），则利用堆排序的方法建立的初始堆
7、为 。A.（79，46，56，38，40，80）B.（84，79，56，38，40，46）C.（84，79，56，46，40，38）D.（84，56，79，40，46，38）二、名词解析（每题3分，共6分）1、算法的时间复杂度：2、二叉排序树：三、填空题（每空2分，共18分）1、从一维数组an中顺序查找出一个最大值元素的时间复杂度为 ，输出一个二维数组bmn中所有元素值的时间复杂度为 。2、在下面数组a中链接存储着一个线性表，表头指针为a0.next ，则该线性表为 。6056423874254376201a 0 1 2 3 4 5 6 7 8datanext3、在循环双向链表中表头结点的左指
8、针域指向 结点，最后一个结点的右指针域指向 结点。4、快速排序在平均情况下的时间复杂度为 ，在最坏情况下的时间复杂度为 。5、已知一棵3阶B 树中含有50个关键字，则该树的最小高度为 ，最大高度为 。四、分析题（每小题4分，共8分）请对下图的无向带权图；（1）写出它的邻接矩阵；（2）并按普里姆算法求其最小生成树。 五、程序填空题（每个空2分，共12分）1、下面的算法，是从串s中删除所有与t相同的子串,并返回删除次数。int SubString_Delete(Stringtype &s,Stringtype t)/从串s中删除所有与t相同的子串,并返回删除次数for(n=0,i=1;i=s0-t
9、0+1;i+)for(j=1;j ) /找到了与t匹配的子串for(k=i;kadjvex;if( & exist_path(k,j) return 1;/i下游的顶点到j有路径/for/else/exist_path_DFS 六、算法设计题（每题8分，16分）1、已知线性表中的元素以值递增有序排列，并以单链表作存储结构。试写一算法，删除表L中所有值大于mink且小于maxk的所有元素。typedef struct LNode ElemType data;struct LNode *next;LNode, LinkList;Status Delete_Between(Linklist &L,int mink,int maxk)2、编写递归算法，求二叉树中以元素值为x的结点为根的子树的深度(求子树深度函数用递归算法)。typedef Struct BiTNodeTElemType data; /数据域Struct BiTNode *lchild, *rchild; /指向其左右孩子结点BiTNode Bitree;int Get_Sub_Depth(Bitree T,int x)专心-专注-专业