数据结构和操作系统试题

《数据结构和操作系统试题》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数据结构和操作系统试题姓名________学号_________得分__________数据结构部分一、判断题。（正确的在括号里打√，错误的打×）①数据元素是数据的最小单位。（）②完全二叉树中，若一个结点没有左孩子，则必是树叶。（）③关键路径是AOE网络中从源点到汇点的最长路径。（）④顺序存储法适用于存储结构为顺序或链式存储的线性表。（）⑤对任何一棵二叉树，如果叶子结点数为n0，度为2的结点数为n2，则n2=n0-1。（）⑥快速排序是一种属于选择排序类的方法，时间效率较高。（）⑦数组的常见操作有存取、修改、删除、插

2、入。（）⑧若非空二叉树中每个结点有两个子结点，且左子树的根小于根结点，右子树的根不小于根结点，则是二叉排序树。（）⑨将一棵树转换为二叉树后，根结点没有左子树。（）⑩在一般情况下，处理冲突方法相同的哈希表，其平均查找长度依赖于哈希表的装填因子。（）二、选择和填空1.在一个长度为n的顺序表（即顺序存储的线性表）中，向第i个元素（1<=i<=n+1）之前插入一个新元素时，需向后移动______个元素。A.n-iB.n-i+1C.n-i-1D.i2.在含n个顶点和e条边的无向图的邻接矩阵中,零元素的个数为_________

3、_。3.某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用________存储方式最节省运算时间。A.单链表B.仅有头指针的单循环链表C.双向循环链表D.仅有尾指针的单循环链表4.若构造一棵具有n个结点的二叉排序树，最坏的情况下其深度不会超过________。A．n/2B．nC．(n+1)/2      D．n+15.对有18个元素的有序表A[1]～A[18]作二分查找，则查找A[3]的比较序列的下标为______。A．1，2，3B.9，5，2，3C.9，5，3D.9，4，2，36.下面

4、程序段的时间复杂度是______________。for(i=0;i

5、不可能是出栈序列。A.CBAEDB.CBEDAC.DBCAED.ACBDEHGFECDBA10.若二叉树共5个叶子，权值分别为{3，4，5，6，7}，则这棵二叉树可能的最短带权路径长度为____________。11.设有二叉树如右图①给出先序遍历的结点访问次序________________②给出中序遍历的结点访问次序________________③给出后序遍历的结点访问次序________________④若用二叉链表作为存储结构，将出现____个空指针域12.以下序列不是堆的是____________。A．

6、（100，85，98，77，80，60，82，40，20，10，66）B．（100，98，85，82，80，77，66，60，40，20，10）C．（10，20，40，60，66，77，80，82，85，98，100）D．（100，85，40，77，80，60，66，98，82，10，20）13.对哈希(HASH)函数H(k)=kMODm,一般来说，m应取_____________。A.素数B.很大的数C.偶数D.奇数14.下面四种方法，___________可以用来处理HASH查找的冲突。A.求余法B.平方取中法

7、C.二分法D.开放地址法三、程序和算法。1.阅读下列C算法，把其中_______处缺少的内容写出来，使之完整，将解答写在右侧空白处。〖说明〗以二叉链表作存储结构，用后序遍历法复制（copy）一个二叉树，即给定一个指向二叉树的指针，生成一个同样结构的二叉树。结点定义structtree{charinfo;structtree*left;structtree*right;};voidcopytree(structtree*nodeptr,structtree*newnodeptr){structtree*copyL,*

8、copyR;if(①){②;③;newnodeptr=(structtree*)malloc(sizeof(structtree));④;⑤;⑥;}2/7}2.简述以下算法的功能和思想。①顺序存储结构线性表aStatuswhatfunc(SqList&a,inti,intk){  if(i<1

9、

10、k<0

11、

12、i+k-1>a.length)returnERROR