2012数据结构期末考试试题.doc

选择题 1．算法分析的目的是①，算法分析的两个主要方面是②。 ①A．找出数据结构的合理性 B．研究算法中的输入和输出的关系 C．分析算法的效率以求改进 D．分析算法的易懂性和文档性 ②A．空间复杂性和时间复杂性 B．正确性和简明性 C．可读性和文档性 D．数据复杂性和程序复杂性 2．在计算机存储器内表示时，物理地址和逻辑地址相同并且是连续的，称之为 A．逻辑结构 　　B．顺序存储结构 C．链表存储结构 　D．以上都不对 3．从一个具有n个结点的单链表中查找其值等于x的结点时，在查找成功的情况下，需平均比较（）个元素结点 A．n/2 B．n C．（n+1）/2 D．（n-1）/2 4．某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（ ）存储方式最节省运算时间。 A．单链表 B．仅有头指针的单循环链表 C．双链表 D．仅有尾指针的单循环链表 5．设单链表中指针p指向结点m，若要删除m之后的结点（若存在），则需修改指针的操作为（） A．p-next=p-next-next; B．p=p-next; C．p=p-next-next; D．p-next=p; 6．在一个单链表中，已知q结点是p结点的前趋结点，若在q和p之间插入s结点，则须执行（） A．s-next=p-next; p-next=s B．q-next=s; s-next=p C．p-next=s-next; s-next=p D．p-next=s; s-next=q 7．在一个具有n个单元的顺序栈中，假定以地址低端（即0单元）作为栈底，以top作为栈顶指针，当做出栈处理时，top变化为（ ） A．top不变 B．top=0 C．top-- D．top++ 8．在具有n个单元的顺序存储的循环队列中，假定front和rear分别为队头指针和队尾指针，则判断队满的条件为（ ） A．rear％n= = front B．（front+l）％n= = rear C．rear％n -1= = front D．(rear+l)％n= = front 9．队列操作数据的原则是（ ）。 A. 先进先出 B. 后进先出 C. 后进后出 D. 不分顺序 10．若串S=software,其子串的数目是（ ） A.8 B.37 C.36 D.9 11．下面的说法中，只有（ ）是正确的 A.串是一种特殊的线性表 B. 串的长度必须大于零 C.串中元素只能是字母 D. 空串就是空白串 12．若将一个10×10阶的对称矩阵压缩存储到一个一维数组中，则该一维数组的大小应该是（ ）。 A、55 B、56 C、45 D、46 13．一个非空的广义表的表尾（ ） A.不能是子表 B.只能是子表 C.只能是原子 D.是原子或子表 14．对稀疏矩阵进行压缩存储目的是（ ） A．便于进行矩阵运算 B．便于输入和输出 C．节省存储空间 D．降低运算的时间复杂度 15．树的先根序列等同于与该树对应的二叉树的（ ） A．先序序列 B．中序序列 C．后序序列 D．层序序列 16．设树T的度为4，其中度为1，2，3和4的结点个数分别为4，2，1，1，则T中的叶子数为（ ） A．5 B．6 C．7 D．8 17．n个顶点，e条边的有向图的邻接矩阵中非零元素有 个。 A.n B.2e C.e D.n+e 18．一个带权无向连通图的最小生成树（ ）。 A．有一棵或多棵 . B．只有一棵 C．一定有多棵 D．可能不存在 19．对于顺序存储的有序表 {5，12，20，26，37，42，46，50，64}，若采用折半查找，则查找元素26的比较次数为（ ）。 A、2 B、3 C、4 D、5 20．折半查找要求查找表( ) A.有序、顺序存储 B.有序、链式存储 C.无序、顺序存储 D.无序、链式存储 21．下列序列中，构成小根堆的是（ ） A．（1，2，5，3，4，6，7，8，9，10） B．（10，5，8，4，2，6，7，1，3） C．（10，9，8，7，3，5，4，6，2） D．（1，2，3，4，10，9，8，7，6，22．______________是稳定的排序方法。 A．起泡