《云南专升本》由会员分享，可在线阅读，更多相关《云南专升本（17页珍藏版）》请在金锄头文库上搜索。
1、一、单项选择题1. 算法指的是（D ）D.解决问题的有限运算序列2. 线性表采用链式存储时，结点的存储地址（B ）B.连续与否均可3将长度为n的单链表链接在长度为m的单链表之后的算法的时间复杂度为（C）A. O（ 1 ）B. O（ n）C. O（ m）D. O（ m+n）4. 由两个栈共享一个向量空间的好处是：（B）B.节省存储空间，降低上溢发生的机率5. 设数组data m作为循环队列SQ的存储空间，front为队头指针，rear为队尾指针，则执行出队操作后其头指针 front 值为（D）D. front=（ front+1）%m6. 如下陈述中正确的是（A ）A.串是一种特殊的线性表7.
2、若目标串的长度为n,模式串的长度为n/3,则执行模式匹配算法时，在最坏情况下的时间复杂度是（ C ）C. O（n2）8. 个非空广义表的表头（D ）D.可以是子表或原子9. 假设以带行表的三元组表表示稀疏矩阵，则和下列行表02335对应的稀疏矩阵是（A ）10. 在一棵度为3的树中，度为3的结点个数为2，度为2 的结点个数为1，则度为0的结点个数为（ C ）C. 611. 在含n个顶点和e条边的无向图的邻接矩阵中，零元素的个数为（D ） D. n2 2e12. 假设一个有n个顶点和e条弧的有向图用邻接表表示，则删除与某个顶点vi相关的所有 弧的时间复杂度是（ C ） C. O（n+e）13.
3、用某种排序方法对关键字序列（25， 84，21， 47，15， 27，68，35， 20）进行排序时，序列的 变化情况如下：20， 15，21， 25， 47，27，68， 35， 8415，20， 21， 25， 35，27， 47， 68， 8415， 20， 21， 25，27，35， 47， 68， 84则所采用的排序方法是（D ） D快速排序14. 适于对动态查找表进行高效率查找的组织结构是（C ） C.三叉排序树15. 不定长文件是指（B ） B.记录的长度不固定二、填空题16数据的逻辑结构是从逻辑关系上描述数据，它与数据的存储（存储结构）无关，是独立于计算机的.17. 在一个带头
4、结点的单循环链表中，p指向尾结点的直接前驱，则指向头结点的指针head可用 p 表示为 head=。18. 栈顶的位置是随着进栈和退栈操作而变化的。19. 在串S= “structure”中，以t为首字符的子串有12 个.20假设一个9阶的上三角矩阵A按列优先顺序压缩存储在一维数组B中，其中B 0存储矩阵中第1个元素片，,则B 31中存放的元素 a4,.21. 已知一棵完全二叉树中共有768结点，则该树中共有 34 个叶子结点。22. 已知一个图的广度优先生成树如右图所示，则与此相应的广度优先遍历序列为abefcdg 。23. 在单链表上难以实现的排序方法有快速排序和,24在有序表（12，24
5、，36，48，60，72，84）中二分查找关键字72时所需进行的关键字比较次数为2。25多重表文件和倒排文件都归属于多关键字文件。三、解答题（本大题共4小题，每小题5分，共20分）26画出下列广义表的共享结构图形表示P=（z），（x，y），（x，y），x），（z）27请画出与下列二叉树对应的森林。28已知一个无向图的顶点集为a,b, c, d, e，其邻接矩阵如下所示a （1）画出该图的图形；b （2）根据邻接矩阵从顶点a出发进行深度优先遍历和广度优先遍历，写cd出相应的遍历序列深度优先遍历序列为：abdce 广度优先遍历序列 e 为：abedc0123456 7 8 9 10 11 1229
6、已知一个散列表如下图所示：3520334859其散列函数为h（key） =key%13, hi=（h（key）+*h1（key）m 回答下列问题:处理冲突的方法为双重散列法，探查序列为：=0， 1,，m1 其中 hl（key） =key%11+1（1）对表中关键字35，20,33和48进行查找时，所需进行的比较次数各为多少？（2）该散列表在等概率查找时查找成功的平均查找长度为多少？解：（1）对关键字35、20、33和48进行查找的比较次数为3、2、1、1；（2）平均查找长度、单项选择1。下面程序段的时间复杂度是（ D ） for（i=0;i<n;i+）for（j=1；j<m;j+）
7、A ij =0;Do O（m*n）2。 在单链表中,指针 p 指向元素为 x 的结点,实现“删除 x 的后继的语句是（ B ） Bop>；next=p->nextgt；next3。在头指针为head且表长大于1的单循环链表中，指针p指向表中某个结点，若p>next>； next=head,则（D ）D*P的直接后继是尾结点4。判定“带头结点的链队列为空”的条件是（C ） Co Q.front=Qo rear5。设有两个串T和P,求P在T中首次出现的位置的串运算称作（D ） D。子串 定位6。 广义表 A= （a, （b）, （） , （c,d,e）的长度为（D ）D.77。
8、一棵含18个结点的二叉树的高度至少为（C ）序列为ABDECF,中序序列为DBEAFC,则后序序列为（D ）Do DEBFCA9无向图中一个顶点的度是指图中（B ）B。与该顶点相邻接的顶点数10。已知一个图如下所示，从顶点a出发进行广度优先遍历可能得到的序列为（C ） Co11。在下列排序方法中，平均时间性能为O（nlogn）且空间性能最好的是（B ） B。堆 排序12。已知一组关键字为25， 48,36， 72， 79,82,23， 40， 16， 35，其中每相邻两个为有序子 序列。对这些子序列进行一趟两两归并的结果是（A ） A。25, 36, 48, 72,23,40, 79,82,
9、16,3513。设顺序存储的线性表共有123 个元素,按分块查找的要求等分成3块。若对索引表采用顺序查找来确定块,并在确定的块中进行顺序查找,则在查找概率相等的情况下,分块查找成 功时的平均查找长度为（ B ）B。 2314。 索引非顺序文件的特点是（A ）A。主文件无序，索引表有序15。倒排文件的主要优点是（C ）C。便于进行多关键字查询二、填空题（本大题共10小题,每小题2 分,若有两个空格,每个空格1 分,共 20 分）16。 抽象数据类型的特点是将_数据和运算封装在一起,从而现实信息隐藏。17。从顺序表中删除一个元素时,表中所有在被删元素之后的元素均需_前移_一个位置。18。在队列中,
10、允许进行插入操作的一端称为队尾,允许进行删除操作的一端称为_队头_。19。如图两个栈共享一个向量空间，top1和top2分别为指向两个栈顶元素的指针，则“栈满”的判定条件是_top1=top21。20。 设 S1="； good"； ,S2= "；", S3="book",则 S1, S2 和 S3 依次联接后的结果是_ good book_.21。假设三维数组A 10 9 8按行优先顺序存储，若每个元素占3个存储单元，且首地址为100，则元素A9 8的存储地址是_2257.22已知在一棵含有n个结点的树中，只有度为k的分支结点和度为0的叶
11、子结点，则该树中 含有的叶子结点的数目为_（n1） /k）*（k-1） +1_或n （n-1） /k_。23. 能够成功完全拓扑排序的图一定是一个_有向无环图_.24. 如果在排序前，关键字序列已接近正序或逆序,则在堆排序和快速排序两者之中，选用_ 堆排序_较为适当。25. 假设哈希表的表长为m,哈希函数为H （key）,若用线性探查法解决冲突，则探查地址序 列的形式表达为_hi=（H（key）+I）/m_。三、解答题（本大题共4小题,每小题5分，共20分）26假设通信电文使用的字符集为a, b, c, d,e, f,名字符在电文中出现的频度分别为： 34,5， 12， 23,8， 18，试为
12、这6个字符设计哈夫曼编码。请先画出你所构造的哈夫曼树（要 求树中左孩子结点的权值小于右孩子结点的权值）,然后分别写出每个字符对应的编码。27。已知一个图如下所示，其顶点按a、b、c、d、e、f顺序存放在邻接表的顶点表中，请画 出该图的邻接表,使得按此邻接表进行深度优先遍历时得到的顶点序列为acbefd，进行广度优 先遍历时得到的顶点序列为acbdfe.28。已知两个4X5的稀疏矩阵的三元组表分别如下：014160113212218122222342522569342283342544251请画出这两个稀疏矩阵之和的三元组表。解：29。从空树起，依次插入关键字40，8,90,15，62，95,1
13、2，23，56,32，构造一棵二叉排序树.（1）画出该二叉排序树（2）画出删去该树中元素值为90 的结点之后的二叉排序树。1。计算机识别、存储和加工处理的对象被统称为（ BB.数据元素2。在具有 n 个结点的有序单链表中插入一个新结点并使链表仍然有序的时间复杂度是（ B ） B.O（n）3。队和栈的主要区别是（D）D.限定插入和删除的位置不同） D。不会出现上溢的情况5.采用两类不同存储结构的字符串可分别简称为（B ） B.顺序串和链串4. 链栈与顺序栈相比，比较明显的优点是（D6.在目标串T 0n 1=xwxxyxy中，对模式串P 0.。mT=xy进行子串定位操作 的结果是（ C）Co 3)
14、B(a,b,c)7已知广义表的表头为a,表尾为（b,c），则此广义表为（B 8o二维数组A按行优先顺序存储，其中每个元素占1个存储单元若A1 1的存储地址为420,A 33的存储地址为446，则A 5 5的存储地址为（ C ）C.4729。二叉树中第5层上的结点个数最多为（D ）D.3210。下列编码中属前缀码的是（A）A1,01,000,00111。如果某图的邻接矩阵是对角线元素均为零的上三角矩阵，则此图是（D ） D。有向无环 图12。对n个关键字的序列进行快速排序，平均情况下的空间复杂度为（D ） D.O （n logn）13. 对表长为n的顺序表进行顺序查找，在查找概率相等的情况下，查找成功的平均查找长度为(n/2)A.B。C. D.n14。对于哈希函数H （key） =key%13，被称为同义词的关键字是（D ） D。25和5115。稠密索引是在索引表中（）Ao为每个记录建立一个索引项B。为每个页块建立一个索引项C.为每组记录建立一个索引项D。为每个字段建立一个索引项二、填空题（每小题2分，若有两个空格，每个空格1分,共20分）16. 当问题的规模n趋向
