天津大学《计算机软件技术基础(2)》在线作业二.docx

《计算机软件技术基础(2)》在线作业二 一个栈的入栈序列是a,b,c,d,e，则栈不可能的输出序列是（ ）。 A:edcba B:decba C:dceab D:abcde 参考选项：C 若已知一个栈的入栈序列是1,2,3,?,n，其输出序列为P1,P2,P3,?,Pn，若P1=n，则Pi为 （ ）。 A:i B:n-i C:n-i+1 D:不确定 参考选项：C 如果只想得到1000个元素组成的序列中第5个最小元素之前的部分排序的序列，用（ ）方法最快。 A:冒泡排序 B:快速排序 C:希尔排序 D:堆排序 参考选项：B 设有如下的单链表的按序号查找的算法，其时间复杂度为（ ）。 LinkNode *GetNode(Linklist head, int i){ int j; ListNode *p; P = head; j=0; while(p-next i){ p = p-next; j++; } if(i==j)return(p); else return(NULL); } A:O(n2) B:O(2n) C:O(n3 ) D:O(logn 参考选项：B 稀疏矩阵一般的压缩存储方法有两种，即( )。 A:二维数组和三维数组 B:三元组和散列 C:三元组和十字链表 D:散列和十字链表 参考选项：C 天津大学《计算机软件技术基础(2)》在线作业二全文共7页，当前为第1页。 天津大学《计算机软件技术基础(2)》在线作业二全文共7页，当前为第1页。 已知一棵度为m的树中有n1个度为1的结点，n2个度为2的结点，?，nm个度为m的结点，问这棵树中叶子结点为( )。 A:1+ni(I-1) B:1+ni(I+1) C:n1+n2+?+nm D:m·nm 参考选项：C 对下图所示的二叉表，按先根次序遍历得到的结点序列为( )。 A:ABCDHEIFG B:ABDHIECFG C:HDIBRAFCG D:HIDBEFGAC 参考选项：B 直接插入排序在最好情况下的时间复杂度为 （ ）。 A:O(logn) B:O(n) C:O(nlogn) D:O(n2 ) 参考选项：B 如下图所示的二叉树的中序遍历序列是 ( )。 A:abcdgef B:dfebagc C:dbaefcg D:defbagc 参考选项：C 已知一棵权集W={2,3,4,7,8,9}的哈夫曼树，其加权路径长度WPL为( )。 A:20 B:40 C:80 D:160 参考选项：C 引入多道程序的目的是( )。 A:提高实时响应速度 B:增强系统交互能力 C:为了充分利用主存储器 D:充分利用CPU，减少CPU等待时间 参考选项：D 天津大学《计算机软件技术基础(2)》在线作业二全文共7页，当前为第2页。 天津大学《计算机软件技术基础(2)》在线作业二全文共7页，当前为第2页。 下面关于临界区的说法中，错误的是( ) 。 A:进程中，访问临界资源的程序是临界区 B:同时进行临界区的进程必须互斥 C:进入临界区内的两个进程访问临界资源时必须互斥 D:在同一时刻，只允许一个进程进入临界区 参考选项：C 若从二叉树的任一结点出发到根的路径上所经过的结点序列按其关键字有序，则该二叉 树是( ) A:满二叉树 B:哈夫曼树 C:堆 D:二叉查找树 参考选项：C 在下列操作系统中，强调吞吐能力的是( )。 A:分时系统 B:多道批处理系统 C:实时系统 D:网络操作系统 参考选项：B 若在线性表中采用折半查找法查找元素，该线性表应该 ( ) A:元素按值有序 B:采用顺序存储结构 C:元素按值有序，且采用顺序存储结构 D:元素按值有序，且采用链式存储结构 参考选项：C 不带头结点的单链表head为空表的判定条件是（ ）。 A:head==NILL B:head-next==NULL C:head-next==head D:head != NULL 参考选项：A 假定有K个关键字互为同义词，若用线性探测法把这K个关键字存入散列表中，至少要 进行( )次探测。 A:K-1次 B:K次 C:K+1次 D:K(K+1)/2次 天津大学《计算机软件技术基础(2)》在线作业二全文共7页，当前为第3页。参考选项：D 天津大学《计算机软件技术基础(2)》在线作业二全文共7页，当前为第3页。 一棵有124个叶结点的完全二叉树，最多有 ( )个结点. A:247 B:248 C:249 D:251 参考选项：B 设有两个串p和q，求q在p中首次出现的位置的运算称作( )。 A:连接 B:模式匹配 C:求子串 D:求串长 参考选项：B 如果要求一个线性表既能较快地查找，又能适应动态变化的要求，则可采用的方法是()。 A:分块法 B:顺序法 C:二分法 D:哈希法 参考选项：A 二维数组Amn按行序为主顺