过程考核试卷1.doc

一、选择题 1．数据结构被形式地定义为（K，R），其中K是①的有限集合，R是K上的②的有限集合。 ①A．算法 B．数据元素 C．数据操作 D．逻辑结构 ②A．操作 B．映象 C．存储 D．关系 (BD) 3．算法复杂度通常是表达算法在最坏情况下所需要的计算量，O(1)的含义是（ ） A．算法执行一步就完成 　　B．算法执行1秒钟就完成 C．算法执行常数步就完成 D．算法执行可变步数就完成 (C) 4．数据结构研究的内容是（ ）。 A．数据的逻辑结构 B．数据的存储结构 C．建立在相应逻辑结构和存储结构上的算法 D．包括以上三个方面 (D) 6．以下关于数据的逻辑结构的叙述中正确的是（ ）。 A．数据的逻辑结构是数据间关系的描述 B．数据的逻辑结构反映了数据在计算机中的存储方式 C．数据的逻辑结构分为顺序结构和链式结构 D．数据的逻辑结构分为静态结构和动态结构 (A) 7．从逻辑上可以把数据结构分为（ ）两大类。 A．动态结构、静态结构 B．顺序结构、链式结构 C．线性结构、非线性结构 D．初等结构、构造型结构 (C) 10．以下那一个术语与数据的存储结构无关？（ ）【A】 A．栈 B. 哈希表 C. 线索树 D. 双向链表 17．以下属于逻辑结构的是（ ）。【C】 A．顺序表 B. 哈希表 C.有序表 D. 单链表 设一组初始记录关键字序列为(50，40，95，20，15，70，60，45)，则以增量d=4的一趟希尔排序结束后前4条记录关键字为（ ）。 B (A) 40，50，20，95 (B) 15，40，60，20 (C) 15，20，40，45 (D) 45，40，15，20 设一组初始记录关键字序列为(25，50，15，35，80，85，20，40，36，70)，其中含有5个长度为2的有序子表，则用归并排序的方法对该记录关键字序列进行一趟归并后的结果为（ ）。 A (A) 15，25，35，50，20，40，80，85，36，70 (B) 15，25，35，50，80，20，85，40，70，36 (C) 15，25，35，50，80，85，20，36，40，70 (D) 15，25，35，50，80，20，36，40，70，85 时间复杂度不受数据初始状态影响而恒为O(nlog2n)的是（ ）。 A (A) 堆排序 (B) 冒泡排序 (C) 希尔排序 (D) 快速排序 10.下列四种排序中（ ）的空间复杂度最大。 D (A) 插入排序 (B) 冒泡排序 (C) 堆排序 (D) 归并排序 1．下述哪一条是顺序存储结构的优点？（ ） A．存储密度大 B．插入运算方便 C．删除运算方便 D．可方便地用于各种逻辑结构的存储表示 2．下面关于线性表的叙述中，错误的是哪一个？（ ） A．线性表采用顺序存储，必须占用一片连续的存储单元。 B．线性表采用顺序存储，便于进行插入和删除操作。 C．线性表采用链接存储，不必占用一片连续的存储单元。 D．线性表采用链接存储，便于插入和删除操作。 3．若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（ ）存储方式最节省时间。 A．顺序表 B．双链表 C．带头结点的双循环链表D．单循环链表 4．某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（ ）存储方式最节省运算时间。 A．单链表 B．仅有头指针的单循环链表C．双链表 D．仅有尾指针的单循环链表 5．在一个长度为n的顺序表中删除第i个元素(0=i=n)时，需向前移动（ ）个元素 A．n-i B．n-i+l C．n-i-1 D．i 6．从一个具有n个结点的单链表中查找其值等于x的结点时，在查找成功的情况下，需平均比较（）个元素结点 A．n/2 B．n C．（n+1）/2 D．（n-1）/2 7．设单链表中指针p指向结点m，若要删除m之后的结点（若存在），则需修改指针的操作为（ ） A．p-next=p-next-next; B．p=p-next; C．p=p-next-next; D．p-next=p