《884计算机软件基础》由会员分享，可在线阅读，更多相关《884计算机软件基础（6页珍藏版）》请在装配图网上搜索。
1、南京林业大学2013年硕士研究生入学考试初试试题科目代码：884 科目名称： 计算机软件基础 满分：150 分注意: 认真阅读答题纸上的注意事项；所有答案必须写在答题纸上，写在本试题纸或草稿纸上均无效；本试题纸须随答题纸一起装入试题袋中交回！一 选择题（本大题共40小题，每小题1分，共40分）1. 线性表是具有n个（ ）的有限序列（n0）。 A表元素 B字符 C数据元素 D数据项 2. 线性表是（ ）A一个有限序列，可以为空B一个有限序列，不可以为空C一个无限序列，可以为空D一个无限序列，不可以为空3. 线性表采用链式存储时，其地址( )。A. 必须是连续的 B. 部分地址必须是连续的 C.
2、一定是不连续的 D. 连续与否均可以 4 链表是一种采用（ ）存储结构存储的线性表；A顺序 B链式 C星式 D网状5. 下面关于线性表的叙述中，错误的是哪一个？（ ）A线性表采用顺序存储，必须占用一片连续的存储单元。B线性表采用顺序存储，便于进行插入和删除操作。C线性表采用链接存储，不必占用一片连续的存储单元。D线性表采用链接存储，便于插入和删除操作。6. 设单链表中指针p指向结点A，若要删除A之后的结点（若存在），则需修改指针的操作为( )。 Ap-next=p-next-next Bp=p-next Cp=p-next-next Dp-next=p7. 设有三个元素X，Y，Z顺序进栈（进的
3、过程中允许出栈），下列得不到的出栈排列是( )。AXYZ B. YZX C. ZXY D. ZYX8. 以下那一个术语与数据的存储结构无关？（ ）A栈 B. 哈希表 C. 线索树 D. 双向链表9. 对于栈操作数据的原则是（ ）。A. 先进先出 B. 后进先出 C. 后进后出 D. 不分顺序10. 深度为K的二叉数，结点数最多有（ ）A 2K B 2K-1 C 2K-1 D 2K-1-111 在带有头结点的单链表中插入一个新结点时不可能修改（ ） A头指针 B头结点指针域 C开始结点指针域 D其他结点指针域12. 一个栈的输入序列为1 2 3 4 5，则下列序列中不可能是栈的输出序列的是（ ）
4、。 A. 2 3 4 1 5 B. 5 4 1 3 2 C. 2 3 1 4 5 D. 1 5 4 3 2 13. 设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主存储，a11为第一元素，其存储地址为1，每个元素占一个地址空间，则a43的地址为（ ）。A. 35 B. 34 C. 9 D. 1014以下数据结构中，（ ）是非线性数据结构A树 B字符串 C队 D栈15. 若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（ ）存储方式最节省时间。A顺序表 B双链表 C带头结点的双循环链表 D单循环链表16. 循环队列存储在数组A0.m中，则入队时的操作为（
5、）。A. rear=rear+1 B. rear=(rear+1) % (m-1)C. rear=(rear+1) % m D. rear=(rear+1)%(m+1) 17 广义表（）的长度为（ ）A0 B1 C2 D不确定18. 将两个各有n1和n2个元素的有序表(递增)归并成一个有序表，仍保持其递增顺序，则最少的比较次数是( )。 An1 Bn2 Cn1+n2-1 Dmin (n1,n2)19. 广义表L=（a,b）,则tail(tail(L)为（ ）Ab B(b) C() D空表20. 在有n个叶子结点的哈夫曼树中，其结点总数是（ ）An B2n C2n-1 D2n+121 设二叉树的
6、根结点层次为1，所有含有15个结点的二叉树中，最小高度是（ ）A6 B5 C4 D322. 深度为4的三叉树至多有（ ）个结点。A13 B14 C40 D41 23. 当一棵有n个结点的满二叉树按层次从上到下，同层次从左到右将数据存放在一维数组A1.n中时，数组中第i个结点的左孩子为( )。AA2i (2i=n) BA2i+1 (2i+10)&(xL.datai-1) L.datai=L.datai-1; i-; L.datai=x; L.last+; 6. 设某作业占有7个页面，如果在主存中只允许装入4个工作页面(即工作集为4)，作业运行时，实际访问页面的顺序是1， 2， 3， 6， 4，
7、7， 3， 2， 1， 4， 7， 5， 6， 5， 2， 1。试用LRU页面调度算法，列出各自的页面淘汰顺序和缺页中断次数，以及最后留驻主存4页的顺序。(假设开始的4个页面已装入主存)。7什么是死锁？死锁的必要条件什么？怎么防止死锁？8什么是进程？它的基本状态？状态之间转换的原因？五 算法设计题（本大题共5小题，每小题8分，共40分）1 有一无向图以邻接矩阵存储结构的方式存储,给出创建该图的相应算法。 2. 设LA和LB是两个递增有序的单链表，试编写一个算法，将LA和LB归并为一个仍是递增有序的单链表LC。3. 假设有一组数据放在一棵二叉树中，找出其中最大值，并给出最大值所在结点的指针。请设计相应算法。4. 利用信号量机制给出读者-写者的算法。5 医院一门诊室，只允许10人进入室内等候，超过10人只能在外等候，门诊只有一个医生看病，患者看完后即离开门诊室，利用信号量机制给出患者看病过程。科目代码：884 科目名称： 计算机软件基础 第 6 页 共 6 页
884计算机软件基础
