四川大学阶段期中期末考试试题（开卷闭卷）.doc

四川大学期末考试试题（开卷）（20182019 学年第 1 学期） A 卷课程号：303316040 课序号： 课程名称：计算机软件技术基础 I 任课教师： 成绩： 适用专业年级：自动化 2017 级 学生人数：114 印题份数：120 学号： 姓名：考 生 承 诺我已认真阅读并知晓四川大学考场规则和四川大学本科学生考试违纪作弊处分规定（修订） ，郑重承诺：1、已按要求将考试禁止携带的文具用品或与考试有关的物品放置在指定地点；2、不带手机进入考场；3、考试期间遵守以上两项规定，若有违规行为，同意按照有关条款接受处理。考生签名：一、单项选择题（本题共 40 小题，每小题 1.5 分，共 60 分）1. 下面程序段的时间复杂性的量级为（ ） 。int i = 0, s1 = 0, s2 = 0; while(i+ next j+;if(i=j)return(p);elsereturn(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 和 1 12. 判断一个顺序栈 ST（最多元素为 mo）为空的条件是（ ） 。A. ST->top top = 0C. st->top top = mo 13. 有一个 N×N 的下三角矩阵 A，若采用行优先进行顺序存储，每个元素占用 k 个字节，则 Aij(1iN,1ji)元素的相对字节地址（相对首元素地址而言）为（ ） A. (i×(i+1)/2+j-1)×4B. (i×i/2+j)×4 C. (i×(i-1)/2+j-1)×4D. (i×(i-1)/2+j)×4 14. 一个数组元素 ai与（ ）的表示等价。A. 若 S>0，则继续执行；若 S A. 将进程阻塞，插入等待队列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 SequenList int dataMAXSIZE; int length; ; 链表的数据结构为：struct LNode int data; / 数据域 LNode* next; / 指针域; typedef LNode* LinkList;第 4 页，共 5 页 试卷编号：三、 程序设计题（20 分）下面定义的大数类型中假设构造函数、赋值运算符和输出函数均已正确定义，其中大数赋值运 算符和输出函数的实现如下所示。class BigNumprivate:int radix=10000; / 进制，默认为 10000int data2000; / 存储大数的整型数组，从下标 0 开始，每个下标元素存储 5 位整数int len; / 大数长度，即 data0至 datalen-1中存储有数据/* data0至 datalen-1由低位向高位进行存储，如大数 13456789054321，将存储为data 数组54321678901345.下标012.*/public:BigNum(const char*);/ 将一个字符串类型的变量转化为大数BigNum /重载赋值运算符，大数之间进行赋值运算BigNum add(const BigNum / 输出大数;voidvoid BigNum:print()BigNum:print()/输出大数输出大数 intint i;i;for(ifor(i = = lenlen - - 1 1 ; ; i i >=>= 0 0 ; ; i-)i-) coutcout <<<< ai;ai; coutcout <<<< endl;endl; BigNumBigNum n.len;memset(data,0,sizeof(data);memset(data,0,sizeof(data); / datadata 数组所有元素均置为数组所有元素均置为 0 0for(intfor(int i i = = 0 0 ; ; i i < < lenlen ; ; i+)i+) aiai = = n.ai;n.ai; returnreturn *this;*this; / 返回当前大数对象的指针返回当前大数对象的指针 我们可以使用 BigNum a=new BigNum(“123456789054321“);定义大数并赋初值；使用 BigNum b; b=a;对大数赋值；使用 a.print();输出大数 a。请为类 BigNum 编写成员函数 add 和 mul，然后利用它们需要编写程序，求的值，要求 n 由 nii1!键盘输入，n 的允许范围为 1n1000，必须在程序中进行判断。 第 5 页，共 5 页 试卷编号：