《2018年上海市培养单位声学研究所东海研究站866计算机原理之数据结构考研基础五套测试题.doc》由会员分享，可在线阅读，更多相关《2018年上海市培养单位声学研究所东海研究站866计算机原理之数据结构考研基础五套测试题.doc（4页珍藏版）》请在金锄头文库上搜索。
1、2018年上海市培养单位声学研究所东海研究站866计算机原理之数据结构考研基础五套测试题一、填空题1 设有一个空枝，栈顶指针为1000H(十六进制) ，现有输入序列为1，2，3，4，5，经过PUSH ，PUSH ，POP ，PUSH ，POP ，PUSH ，PUSH 之后，输出序列是_，而栈顶指针值是_。设栈为顺序找，每个元素占4个字节。【答案】23；100CH 2 栈是_的线性表，其运算遵循_的原则。【答案】操作受限(或限定仅在表尾进行插入和删除操作) ；后进先出3 组成串的数据元素只能是_。【答案】字符 4 如果按关键码值递增的顺序依次将关键码值插入到二叉排序树中，则对这样的二叉排序树检索
2、时，平均比较次数为_。【答案】 【解析】如果关键码是排好序的，构建二叉排序树就会形成一个单支树，它的查找效率和顺序查找效率一样为。 5 文件由_组成；记录由_组成。【答案】记录；数据项 6 根据线性表的链式存储结构中每一个结点包含的指针个数，将线性链表分成_和_；而又根据指针的连接方式，链表又可分成_和_。【答案】单链表；双链表；(动态) 链表；静态链表【解析】线性表的链式存储结构根据每个结点包含的指针个数分为单链表和双链表，单链表只包含一个指针，指向后续元素，双链表包括两个指针，指向前一个元素和后续元素。根据指针的连接方式，链表可分为动态链表和静态链表。静态链表的指针指向下一个元素的编号，动
3、态链表的指针指向下一个元素的物理位置。 7 设广义表L (（ ），（ ）) ，则head(L)是_tail(L)是_L的长度是_；深度是_。【答案】（ ）；(（ ）) ；2；2【解析】广义表的表头是表的第一个元素，表尾是除了第一个元素外其余的所有的元素构成的表；表的长度指表中元素的个数；表的深度指展开后括号的层数。 8 下面描述的是一种构造最小生成树算法的基本思想。设要处理的无向图包括n 个顶点用相邻矩阵A 表示，边的权全是正数。请在下列划线处填上正确叙述。(1)若是边，则的值等于_，若不是边，则A(i, j) 的值是一个比任何置边的权_，矩阵的对角线元素全为0。(2)构造最小生成树过程中，若
4、顶点已包括进生成树，就把相邻矩阵的对角线元素成_，若【答案】(1)已包括进生成树，就把矩阵元素置成_。(3)算法结束时，相邻矩阵中_的元素指出最小生成树的_。边上的权值；都大的数；(2)1; 负值；(3)为负；边 9 一个字符串中_称为该串的子串。【答案】任意个连续的字符组成的子序列 10一个算法具有5个特性: _、_、_、有零个或多个输入、有一个或多个输出。【答案】有穷性；确定性；可行性 11已知链队列的头尾指针分别是f 和r ，则将值x 入队的操作序列是_。【答案】S (LinkedList*)malloc(sizeof (LNode)；s data x ；s next r next ；r
5、 next s ；r s ；【解析】队列采用链式存储结构，先分配一个节点的内存，然后在队尾添加该节点。12下列程序是快速排序的非递归算法，请填写适当的语句，完成该功能。 a 中存放待排序的关键字 【答案】 【解析】快速排序(quick sort)的基本思想是，通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。 二、单项选择题13若线性表最常用的操作是存取第I 个元素及其前驱和后继元素的值，为节省时间应采用的存储方式（ ）。A. 单链表 B. 双向链表 C. 单循环链表 D. 顺序表 【答案】D【解
6、析】线性表采用顺序表，便于进行存取任一指定序号的元素。14某机器有一个标志寄存器, 其中有进位/借位标志CF 、零标志ZF 、符号标志SF 和溢出标志OF , 条件转移指令bgt(无符号整数比较大于时转移) 的转移条件是（ ）。A.CF+OF=0 B.SF+ZF=0 C.CF+ZF=0 D.CF+SF=0 【答案】C【解析】判断无符号整数AB成立, 满足的条件是结果不等于0, 即零标志ZF=0, 且不发生进位, 即进位/借位标志CF=0。所以正确选项为C 。其余选项中用到了符号标志SF 和溢出标志OF , 显然可以排除掉。 15将森林F 转换为对应的二叉树T , F 中叶结点的个数等于（ ）A.T 中叶结点的个数 B.T 中度为1的结点个数一、填空题考研试题
