数据结构(A卷)试题.doc

湖南人文科技学院 通控系 通信工程专业2007级 200 9---2010 学年第 一 学期 数据结构 课程考核试卷(A) 考核方式: （闭卷) 考试时量：120 分钟 题 号 一 二 三 四 总分 合分人 复查人 实得分 评卷人 一、填空题：（每空1 分，共 20 分） 1、数据结构被形式地定义为（D, R），其中D是 的有限集合，R是D上的 有限集合。 2、一个算法的效率可分为 效率和 效率。 3、在n个结点的单链表中，查找某个数据的时间复杂度为_______________。n个结点的顺序表存储时，查找某个数据的时间复杂度为_______________。 4、在一个循环队列中，队首指针指向队首元素的 位置。 5、在具有n个单元的循环队列中，队列满时共有 个元素。 6、设串t=“I am a student good”，串Sub=Substring(t,8,7)，那么Sub= __________。 7、假设有二维数组A6×8，每个元素用相邻的6个字节存储，存储器按字节编址。已知A[0][0]的存储位置为1000，按行优先存储，则A[3][4]的地址为 ；若按列优先存储时，则A[3][4]的地址为 。 8、设一棵完全二叉树中有21个结点，如果按照从上到下、从左到右的顺序从1开始顺序编号，则编号为8的双亲结点的编号是___________，编号为8的左孩子结点的编号是_____________。 9、在解决计算机主机与打印机之间速度不匹配时通常设置一个打印数据缓冲区，主机将要输出的数据依次写入该缓冲区，而打印机从该缓冲区中取出数据打印。该缓冲区应该是一个_________ 结构，其主要特点是__________。 10、算法是指令的有限序列，其中每一条指令表示一个或多个操作，此外，一个算法还具有五个重要特性，它们分别是 __________、___________、_____________ 、有零或多个输入和有一或多个输出。 11、在一个稀疏矩阵中，每个非零元素所对应的三元组包括该元素的____________、____________和_______ 三项。 得分 评卷人 二、选择题：（每空2分，共30分） 共 7 页第 1 页 1．（ ）是具有相同特性数据元素的集合，是数据的子集。 A.数据符号 B.数据对象 C.数据 D.数据结构 2．用链表表示线性表的优点是 ( )。 A.便于随机存取 B.花费的存储空间比顺序表少 C.便于插入与删除 D.数据元素的物理顺序与逻辑顺序相同 3．堆栈的输入序列为（A,B,C,D），不可能的输出有（ ）。 A.(A,B,C,D) B. (D,C,B,A) C. (A,C,D,B) D . (C,A,B,D) 4．在数组表示的循环队列中，front、rear分别为队列的头、尾指针，maxSize为数组的最大长度，队满的条件是( )。 A. front=maxSize B. (rear+1)%maxSize=front C. rear=maxSize D. rear=front 5．设有一个对称矩阵A，采用压缩存储方式，以行序为主序存储a11为第一个元素，其存储地址为1，每个元素占一个地址空间，则 a85地址为（ ）。 A. 23 B. 33 C. 18 D. 40 6．若已知一棵二叉树先序序列为ABCDEFG，中序序列为CBDAEGF，则其后序序列为( ) 。 A. CDBGFEA B. CDBFGEA C. CDBAGFE D. BCDAGFE 7．采用折半查找方法进行查找，数据文件应为（ ），且限于（ ）。 A.有序表 顺序存储结构 B.有序表 链式存储结构 C.随机表 顺序存储结构