数据结构模拟试题一
- 格式：doc
- 大小：53.00 KB
- 文档页数：6
数据结构模拟试题一
一、单选题（每小题2分，共8分）
1、在一个长度为n的顺序存储的线性表中，删除第i个元素（1≤i≤n）时，需要从前向后依次前移 个元素。
A n-i B n- i十1
C n-j-1 C i
2、设一个广义表中结点的个数为n，则求广义表深度算法的时间复杂度为
。
A O（1） B O（n）
C O（n2） D O（1og2n）
3、假定一个顺序队列的队首和队尾指针分别为1和r，则判断队空的条件为
。
A f+ 1= =r B r＋1= =f
C f= =0 D f= =r
4、从堆中删除一个元素的时间复杂度为 。
A O（1） B O（n）
C O（1og2n） D O（nlog2n）
二、填空题（每空1分，共32分）
1、在线性结构、树结构和图结构中，前驱和后继结点之间分别存在着
、
和 的联系。
2、在线性表的单链接存储中，若一个元素所在结点的地址为p，则其后继结点的地址为
，若假定p为一个数组a中的下标，则其后继结点的下标的
。
3、在初始化一个稀疏矩阵的函数定义中，矩阵形参应说明为 参数。
4、栈又称为 表，队列又称为 表。
5、后缀表达式“4 5+3*2 4+ *”的值为 。
6、一棵深度为5的满二叉树中的结点较为 个，一棵深度为3的满四叉树中的结点数为 个。 7、对于一棵含有40个结点的理想平衡树，它的高度为 。
8、从一棵二叉搜索树中查找一个元素时，若元素的值等于根结点的值，则表明
，若元素的值小于根结点的值，则继续向 查找，若元素的大于根结点的 查找。
9、当从一个小根堆中删除一个元素时，需要把
元素填补到 位置，然后再长条件把它逐层
调整。
10、对于一个具有n个顶点的图，若采用邻接炬阵表示，则矩阵大小为
。
11、对于一个具有n个顶点和e条边的连通图，其生成树中的顶点数和边数分别为
和 。
12、二分查找过程所对应的判定树既是一棵 ，又是一棵
。
13、若长度n=10000的线性表进行二级索引存储：每级索引表中的索引项是下一级20个记录的索引，则一级索引表的长度为 ，二级泵引表的长度为
。
14、在一棵20阶的B-树中，每个非树根结点的关键字数目最少为 个，最多为 个。
15、每次直接或通过基准元素间接比较两个元素，若出现逆序排列时就交换它们的位置，此种排序方法叫做 排序；每次使两个相邻的有序表合并成一个有序表的排序方法叫做 排序。
16、在归并排序中，进行每趟归并的时间复杂度为 ，整个排序过程的时间复杂度为 ，空间复杂度为 。
三、运算题。（每小题6分，共24分）
1．假定一棵普通树的广义表表示为：a（b（e），c（f（h，i，j），g），分别写出先根、后根、按层遍历的结果。
先根： 。
后根： 。 按层： 。
2．己知一个带权图的顶点集V和边集6分别为：
V={0，1，2，3，4，5，6，7}；
E={（0，1）8，（0，2）5，（0，3）2，（1，5）6，（2，3）25，（2，4）13，（3，5）9，（3，6）10，（4，6）4，（5，7）20；
则求出该图的最小生成树的权。
最小生成树的权： 。
3．对于线性表（18，25，63，50，42，32，90，66）进行散列存储时，若选用H（K）=K％9作为散列函数，则散列地址为0的元素有 个，散列地址为3的元素有 个，散列地址为5的元素有 个。
4．假定一组记录的排序码力（46，79，56，38，40，80，25，34），在对其进行快速排序的过程中，对应二叉搜索村的深度为 ，分支结点数为
。
四、阅读算法，回答问题（每小题8分，共16分）
1、 void AA（Lnode *&HL）
{
InitList（HL）；
InsertRear（HL，30）；
InsertRear（HL，50）；
int a[5]={15，8，9，26，12}；
for}int i=0；i<5；i++） InsertFront（HL，a[ i ]）；
}
该核算法被调用执行后，得到的以HL为表头指针的单链表中的数据元素依次为：
。
2、 void AA（Heap&HBT，const Elem type item）
//HBT为一个小根堆
{
HBT.heap[HBT.size]=item;
HBT.size++； eLemType x=item；
int i=HBT.size—1；
while（i！=0）{
int j=（i—1）/2；
if（x>=HBT.heap[j]）break;
HBT.heap[i]=HBT.heap[j];
i=j;}HBT.heap[i]=x;
}
该算法的功能为：
。
五、算法填空，在画有横线和地方填写合适的内容（10分）
从一维数组A[n]中二分查找关键字为K的元素的递归算法，若查找成功则返回对应元素的下标，否则返回—1。
int Binsch（Elem Type A[]，int low，int high，Key Type K）
{
if（low<=high）
{
int mid=（low+high）/2；
if（K= =A[mid].key） ；
else if(K
else
}
else return—1；
}
六、编写算法（10分）
编写在以BST为树根指针的二叉搜索树上进行查找值为item的结点的非递归算法，若查找item带回整个结点的值并返回ture，否则返回false。
bool Find（BtreeNode*BST，ElemType&item）
参考答案
一、单选题（每小题2分，共8分） 评分标准：选对者得2分，否则不得分。
1、A 2、B 3、D 4、C
二、填空题（每空1分，共32分）
评分标准：每空得1分，否则不得分。
1、1：1 1：N M：N （或者1对1 1对N M对N）
2、p—>next a[p]. next
3、引用
4、后进先出 先进先出
5、162
6、31 21
7、6
8、查找成功 左子树 右子树
9、堆尾 堆顶 向下
10、n2
11、n n一1
12、二叉搜索树理想平衡树（次序无先后）
13、500 25
14、9 19
15、交换 二路归并
16、 （）（n） （）（nlog2n） （）（n）
三、运算题（每小题6分，共24分）
1．先根：a，b，e，c，f，h，i，j，g，d；（2分）
后根：e，b，h，I，j，f，g，c，d，a；（2分）
按层：a，b，c，d，e，f，g，h，i，j（2分）
2．最小生成树的权：55
3．3 1 2 每个数据占2分
4．5 6 每个数据占3分
四、阅读算法，回答问题（每小题8分，共16分）
1．（12，26，9，8，15，30，50）
评分标准：有一处错误扣4分，两处及以上错误不得分。 2，向HBT堆中插入一个值为item的元素，使得插入后仍是一个堆。
评分标准：请根据叙述情况酌情给分。
五、算法填空，在画有横线的地方填写合适的内容（10分）。
return mid
return Binsch（A ，1ow，mid一1 ，K）
return Binsch（Atmid十1，high，K）
评分标准：对一空得3分，全对得10分。
六、编写算法（10分）
评分标准：请根据编程情况酌情给分。
bool Find（BtreeNode*BST，ElernType＆item）
{
while（BST！一NULL）
{
if（item= =BST一>data）{item=BST一>data； return true;}
else if（item＜BST一>data＝BST＝BST一>left;
else BST=BST一>right；
}
return false;
}
