四川大学期末考试试题开卷2018——2019学年第1学期A卷.doc

四川大学期末考试试题（开卷）（20182019学年第 1 学期） A卷课程号： 课序号： 课程名称：计算机软件技术基础I 任课教师： 成绩：适用专业年级：自动化2017级 学生人数：114 印题份数：120 学号： 姓名：考 生 承 诺我已认真阅读并知晓四川大学考场规则和四川大学本科学生考试违纪作弊处分规定（修订），郑重承诺：1、已按要求将考试禁止携带的文具用品或与考试有关的物品放置在指定地点；2、不带手机进入考场；3、考试期间遵守以上两项规定，若有违规行为，同意按照有关条款接受处理。考生签名：一、单项选择题（本题共40小题，每小题1.5分，共60分）1. 下面程序段的时间复杂性的量级为（ ）。int i = 0, s1 = 0, s2 = 0;while(i+ next & jnext; j+; if(i=j) return(p); else return(NULL);A. O(n2) B. O(n) C. O(n3) D. O(logn) 9. 假定一个链式队列的队首和队尾指针分别用front和rear表示，每个结点的结构为：，当出列时所进行的指针操作为（ ） A. front = front-next; B. rear = rear-next; C. front-next = rear; rear = rear-next; D. front = front-next; front-next = rear; 10. 如果进栈序列为e1,e2,e3,e4，则可能的出栈序列是（ ）。A. e3，e1，e4，e2B. e2，e4，e3，e1C. e3，e4，e1，e2D. 以上均有可能11. 若用一个大小为6的数组来实现循环队列，且当前rear和front的值分别为0和3。当从队列中删除一个元素，再加入两个元素后，rear和front的值分别为（ ）。A. 1和5B. 2和4C. 4和2D. 5和112. 判断一个顺序栈ST（最多元素为mo）为空的条件是（ ）。A. ST-top 0B. ST-top = 0C. st-top moD. st-top = mo13. 有一个NN的下三角矩阵A，若采用行优先进行顺序存储，每个元素占用k个字节，则Aij(1iN,1ji)元素的相对字节地址（相对首元素地址而言）为（ ） A. (i(i+1)/2+j-1)4B. (ii/2+j)4C. (i(i-1)/2+j-1)4D. (i(i-1)/2+j)414. 一个数组元素ai与（ ）的表示等价。A. &a + iB. *(a + i) C. *a + iD. a + i15. 二维数组M的元素是4个字符（每个字符占一个存储单元）组成的串，行下标i的范围从0到4，行下标j的范围从0到5，M按行存储时元素M35的起始地址与M按列存储时元素（ ）的起始地址相同。A. M24 B. M34 C. M35 D. M4416. 对一棵完全二叉树，按从上至下、从左至右的方式从1开始进行编号。若编号为i的结点存在左孩子，则左孩子结点的编号为（ ）。 A. 2iB. 2i-1C. 2i+1D. 2i+217. 利用3，6，8，12这4个值作为叶子结点的权，生成一棵哈夫曼树，该树的带权路径长度为（ ）A. 29B. 38C. 55D. 5818. 向二叉搜索树中插入一个元素时，其时间复杂度大致为（ ）。A. O(1) B. O(log2n) C. O(n) D. O(nlog2n)19. 线索二叉树是一种（ ）结构。A. 逻辑B. 逻辑和存储图C. 物理D. 线性第 2 页，共 5 页试卷编号：20. 设高度为h的二叉树上只有度为0或度为2的结点，则此类二叉树中所包含的结点数至少为（ ）。A. 2hB. 2h-1C. 2h+1D. h21. 对于长度为9的顺序存储的有序表，若采用二分查找，在等概率情况下的平均查找长度为（ ）的值除以9。A. 18B. 20C. 22D. 2522. 对线性表进行二分查找时，要求线性表必须（ ）。A. 以顺序方式存储B. 以顺序方式存储，且结点按关键字有序排序C. 以链接方式存储D. 以链接方式存储，且结点按关键字有序排序23. 若查找每个元素的概率相等，则在长度为n的顺序表上查找任一元素的平均查找长度为（ ）。A. nB. n + 1C. (n - 1)/2D. (n + 1)/224. 链表适用于（ ）查找。A. 顺序B. 二分法C. 顺序，也能二分法D. 随机25. 一组记录的关键码为（46，24，57，23，40，15），则利用选择排序的方法，第二趟排序的结果是（ ）。A. 15，46，57，24，40，23B. 15，23，57，46，40，24C. 15，23，24，46，40，57D. 15，23，24，40，46，5726. 从未排序的序列中依次取出元素与已排序序列中的元素进行比较，然后将其放在排序序列的合适位置，该排序方法称为（ ）排序法。A. 选择B. 希尔C. 插入D. 冒泡27. 以下结点序列是堆的为（ ）。A. 100,90,80,60,85,75,20,25,10,70,65,50B. 100,70,50,20,90,75,60,25,10,85,65,80C. 100,80,90,60,85,75,20,25,10,70,65,50D. 100,50,70,20,90,75,60,25,10,85,65,8028. 下列关键字序列中，（ ）是堆。A. 16, 72, 31, 23, 94, 53B. 94, 23, 31, 72, 16, 53C. 16, 53, 23, 94，31, 72D. 16, 23, 53, 31, 94, 7229. 工业过程控制系统中，运行的操作系统最好是（ ）。A. 分时系统B. 实时系统C. 分布式操作系统D. 网络操作系统30. 现代操作系统的两个基本特征是（ ）和资源共享。A. 多道程序设计B. 中断处理C. 程序的并发执行D. 实现分时与实时处理31. 在下列操作系统中强调并行性的操作系统是（ ）A. 分时系统B. 实时系统C. 分布式操作系统D. 网络操作系统32. 在任何时刻，一个进程的状态变化（ ）引起另一个进程的状态变化。A. 必定B. 一定不C. 不一定D. 不可能33. 引入多道程序的目的是（ ）。A. 提高实时响应速度B. 增强系统交互能力C. 为了充分利用主存储器D. 充分利用CPU，减少CPU等待时间34. V操作词V(S)，S为一信号量，执行V操作时完成以下操作：S=S+1;若S0，则继续执行；若SA. 将进程阻塞，插入等待队列B. 将队列中的一个进程移出，使之处于运行状态C. 将进程变为挂起状态D. 将队列中的一个进程移出，使之处于就绪状态第 3 页，共 5 页试卷编号：35. 在单一处理器上，将执行时间有重叠的几个程序称为（ ）。A. 顺序程序B. 多道程序C. 并发程序D. 并行程序36. 进程间的基本关系为（ ）。A. 相互独立与相互制约B. 同步与互斥C. 并行执行与资源共享D. 信息传递与信息缓冲37. 分页式存储管理的主要特点是（ ）A. 不要求作业同时全部装入主存B. 不要求作业装入到主存的连续区域C. 要求扩充主存容量D. 要求处理缺页中断38. 页式存储管理中，页表的大小由（ ）决定。A. 作业所占页的多少B. 计算机编址范围C. 操作系统D. 系统统一指定39. 可由CPU调用执行的程序所对应的地址空间为（ ）。A. 名称空间B. 虚拟地址空间C. 相对地址空间D. 物理地址空间40. 若处理器有32位地址，则它的虚拟地址空间为（ ）字节。A. 2GBB. 4GBC. 100KBD. 640KB二、 编程题（20分）分别编写在非递减有序顺序表和带头结点的非递减有序单链表上统计出值界于x、y（要求x不超过y）之间的元素个数的函数，统计结果由函数值返回。分析函数的时间复杂度和空间复杂度。假设，顺序表的数据结构为：const int MAXSIZE=100;struct SequenListint dataMAXSIZE;int length;链表的数据结构为：struct LNodeint data; / 数据域LNode* next; / 指针域;typedef LNode* LinkList;第 4 页，共 5 页试卷编号：三、 程序设计题（20分）下面定义的大数类型中假设构造函数、赋值运算符和输出函数均已正确定义，其中大数赋值运算符和输出函数的实现如下所示。class BigNumprivate: int radix=10000; / 进制，默认为10000 int data2000; / 存储大数的整型数组，从下标0开始，每个下标元素存储5位整数 int len; / 大数长度，即data0至datalen-1中存储有数据/* data0至datalen-1由低位向高位进行存储，如大数321，将存储为data数组54321678901345.下标012.*/public: BigNum(const char*);/ 将一个字符串类型的变量转化为大数 BigNum & operator=(const BigNum &);/重载赋值运算符，大数之间进行赋值运算 BigNum add(const BigNum &)/ 两个大数相加 BigNum mul(const BigNum &)/ 两个大数相乘 void print();/ 输出大数;void BigNum:print()/输出大数 int i; for(i = len - 1 ; i = 0 ; i-) cout ai; cout endl;BigNum &BigNum:operator=(const BigNum &n) / 重载赋值运算符，大数之间进行赋值运算 len = n.len; memset(data,0,sizeof(data); / data数组所有元素均置为0 for(int i = 0 ; i