计算机软件基础考试试题答案

三峡大学 试卷纸 教学班号 序号 学号 姓名 命题教师 审题教师 …………………….………….……试 题 不 要 超 过 密 封 线………….……………………………… 学年第 一 学期 《计算机软件技术基础》抽查试卷 注意：1、本试卷共  4  页；              2、考试时间120分钟                    3、姓名、学号必须写在指定地方    阅卷负责人签名：                  题 号 一 二 三 四 五 六 七 八 总 分 得 分                                       阅卷人 得分         一、填空题 (15×2＝30分) 1． 某完全二叉树共有700个节点，那么该二叉树的高度为__10__，叶子节点数目为_376_。 2. 已知一有向图的邻接矩阵如下图所示（各顶点依次编号为1，2，3，4，5，6）： 0 1 0 1 0 0 0 0 1 0 1 0 1 0 0 1 0 0 0 0 0 0 0 1 0 0 1 0 0 0 0 0 1 0 1 0             A= 那么该图__是___（是否）为连通图。编号为3的顶点的出度为__2____；入度为___3__。 如果从编号为1的顶点出发对该图进行深度优先遍历，其得到的遍历序列为___123465___； 如果从编号为3的顶点出发对该图进行广度优先遍历，其得到的遍历序列___341625____。 3．设三个元素的入栈序列为b，c，a，那么不可能的出栈序列为__abc___。 4. 一个顺序存储的循环队列最大能存储的元素数目是100，那么设队头指针(约定为指向队头 元素前一位置)和队尾指针的值分别是13和89，那么队列中实际存储元素的个数是__76__； 若队头指针和队尾指针的值分别是89和13，那么队列中实际存储元素的个数是__24__。 5. 顺序查找一个具有n个元素的线性表，其时间复杂度为 ；二分查找一个具有n个 元素的顺序存储的线性表，其时间复杂度为 。 6. 已知一二叉树的先序遍历和中序遍历得到的序列为ABECFGHD和EBAFHGCD，那么该二叉树的 后序遍历得到的序列是________。 7. 快速排序的平均时间复杂度为 ；而当初始数据的关键字有序时，那么快速排序的时间复杂度为 。 阅卷人 得分         二、选择题（8×3＝24分） 1．顺序存储队列Q的入队操作可描述为：[  ] A．Q.V[rear++]=x                        B．Q.V[++rear]=x  C．Q.V[Q.rear++]=x                      D．Q.V[++Q.rear]=x 2．已知某二叉树度为1的结点数是100， 总结 初级经济法重点总结下载党员个人总结TXt高中句型全总结.doc高中句型全总结.doc理论力学知识点总结pdf 点数是199， 那么该二叉树的叶子结点数是：[  ] A．49      B．50        C．51          D．52 3．设T为Huffman树，它有6个树叶，且各树叶的权分别为2，3，4，5，6，7。 那么该树的非叶子结点的权之和为：[  C ] A．63      B．70        C．68          D．69 4．一棵二叉树的顺序存储结构如下图所示，若中序遍历该二叉树，则遍历次序为：[  ] A B C D E   F       G     H                             A．ABDEGCFH      B．DBEGACHF    C．ABCDEFGH    D．DGEBHFCA 5．从未排序序列中挑选元素，并将其放入已排序序列中，此排序方法称为：[ A  ] A．插入排序        B．选择排序        C．冒泡排序        D．快速排序 6．若一个有向完全图有n个顶点，那么该有向图的弧的数目是：[ C ] A．n!              B．n!/2            C．n*(n-1)          D．n*(n-1)/2 7．某有序表的关键字分别为：13，33，36，58，70，75，88，90，96，102。那么利用折 半查找算法进行查找时的平均查找长度为：[  ] A．2.0            B．2.9              C．2.5              D．3.0 8．利用一组关键字（20，15，10，50，60，30，17，53，13）构成二叉排序树，那么该二 叉树的平均查找长度是：[ C  ] A．20/9            B．2                C．25/9              D．16/9 阅卷人 得分         三、简答题 (6+10＝16分) 1．已知一组数据元素为（54，46，75，18，27，15，39，67，88）。写出分别利用选择排序、插入排序、冒泡排序、快速排序以及2路归并排序的第一趟排序结果（只需要写出结果）。 答：选择排序： 15  54  46  75  18  27  39  67  88 插入排序  46  54  75  18  27  15  39  67  88 冒泡排序  46  54  18  27  15  39  67  75  88 快速排序  39  46  15  18  27  54  75  67  88 2路归并  46  54  18  75    15  27  39  67  88 2． 假定一个表为 (6,17,22,1,14,8,11,9,28)，散列空间为[0…10]，采用除留余数法构造表，哈希函数为H(K)=K MOD 11，分别用线性探测法以及链地址法解决地址冲突，试画出在这两种方法下得到的哈希表以及等概率情况下的平均查找长度（只需要写出结果）。 解：因为： 6      MOD 11=6    则6存放第6个空间中；                    17  MOD 11=6    发生冲突，放入下一个地址空间中可行，即第7个空间中； 22     MOD 11=0    则22放入第0个空间中； 1    MOD 11=1      存入第1个空间中； 14  MOD 11=3    则14存于第3个空间中； 8  MOD 11=8      则8存于第8个空间中； 11    MOD 11=0      冲突，下一地址空间为第1个空间，仍然冲突，再选择下一地址空间，即第2个空间中，可行。 9  MOD 11=9    则9存于第9个空间中； 28  MOD 11=6  冲突，下一地址为第7个空间，仍然冲突；再下一地址空间为第8个空间，仍然冲突；再下一地址空间为第9个空间，仍然冲突；再下一地址空间为第10个空间，可行。 下标 0 1 2 3 4 5 6 7 8 9 10 数据 22 1 11 14     6 17 8 9 28                         则哈希表为：                                                        （8分） 平均查找长度为： ASL=(1+2+1+1+1+1+3+1+5)/9=16/9                                    （2分） 阅卷人 得分         四、(10分)二叉树定义如下： typedef  struct  btnode { int data;                      /*存储数据信息*/ struct btnode *lchild,*rchild;    /*左、右孩子节点指针*/ }BTNODE;    设二叉树T是一棵二叉排序树，试设计一个算法，实现在T中查找数据信息为x的结点，如果找不到，则给出查找失败信息；否则返回该结点指针。部分代码已经给出，请把程序补充完整。 BTNODE  *SearchNode (BTNODE  *T) { BTNODE  *p; p=T;        /*变量初始化*/ /*查找过程*/ while ( __p!=NULL__ ) { if( ___p->data==x______ )  /*找到*/ return  p;; else if ( __p->data>x___ )                  ___p=p->lchild___; else ___p=p->rchild___; } printf(“查找失败\n”);exit(1); } 阅卷人 得分         五、（共10分）线性表定义如下： typedef  struct  list{ int    key;           /*关键字*/ ohtertype    info ;    /*其他信息 */ }LIST;    用C语言编程实现在一个顺序存储的递增有序线性表中进行二分查找的递归算法，已知被查找元素的关键字为x,要求返回该元素在顺序线性表中的位置。部分源代码已经给出，请把程序补充完整。 /*程序开始*/ int binsearchList(LIST A[] , int low, int high, int x ) {  int mid; if( _low<=high__ ) { mid=(low+high)/2;