一．选择题：
1．数据结构是研究数据的 ( ) 以及它们之间的相互关系
A．理想结构，物理结构 B．理想结构，抽象结构
C．物理结构，逻辑结构 D．抽象结构，逻辑结构 2. 组成数据的基本单位是（ ）
A.数据项 B.数据类型 C. 数据元素 D. 数据变量 3. 如果某数据结构的数据元素的集合为S={A,B,C,D,E,F,G}，元素之间的关系为
R={ A.插入 B.读表元 C.查找 D.定位 5. 设一数列的输入顺序为1，2，3，4，5，6通过栈操作不可能排成的输出序列为（ A. 3，2，5，6，4，1 B. 1，5，4，6，2，3 C. 2，4，3，5，1，6 D. 4，5，3，6，2，1 6. 设字符串S1=‘ABCDEFG’，S2=‘PQRST’则运算S=Concat(Sub(S1,2,Length(S2)), Sub(S1,Length(S2),2))后结果为（ ） A.‘BCQR’ B.‘BCDEF’ C.‘BCDEFG’ D.‘BCDEFEF’ 7. 设单链表中指针P指向结点A，若要删除A之后的结点（若存在），则修改指针的 操作为（ ） A. p→next= p→next→next B. p= p→next C. p= p→next→next D. p→next = p 8. 线性表采用链式存储时，其地址（ ） A. 必须是连续的 B.部分地址必须是连续的 C. 一定是不连续的 D.连续与否均可以 9. 在内部排序时，排序不稳定的有（ ） A.插入排序 B. 冒泡排序 C. 快速排序 D.归并排序 10. 设有1000个元素，用折半法查找时，最小比较次数为（ ） A.0 B. 1 C.10 D. 500 11. 将一个元素进入队列的时间复杂度是（ ） A. O (1) B. O (n) C. O (n2) D. O (log2n) 12. 在一个具有n个结点的单链表中查找其值等x的结点，在查找成功的情况下， 需要比较（ ）个元素结点 1 ） A. n/2 B. n C. (n+1)/2 D. (n-1)/2 13. 从一个长度为n的顺序表中删除第i个元素(1≤i≤n)，需向前移动（ ）个元素 A. n-i B. n-i+1 C. n-i-1 D. i 14. 总共3层的完全二叉树，其结点数至少有（ ） A.3 B. 4 C.7 D.8 15. 队列操作的原则是（ ） A. 先进先出 B.后进先出 C. 只能进行插入 D. 只能进行删除 16. 若线性表最常用的操作是存取第i个元素及其前驱元素的值，则采用（ ） 存储方式最节省时间 A.单链表 B. 双向链表 C. 音循环链表 D. 顺序表 17. 栈和队列都是（ ） A. 顺序存储的线性结构 B. 限制存取点的线性结构 C. 链接存储的线性结构 D. 限制存取点的非线性结构 18. 与线性表的链接存储相符的特性是（ ） A.插入和删除操作灵活 B. 需要连续存储空间 C. 便于随机访问 D. 存储密度大 19.若进队序列为1,2,3,则出队序列是（ ） A.3，2，1 B. 1，3，2 C. 1，2，3 D. 3，2，1 20. 在单向循环链表中，若头指针为h，那么p所指结点为尾结点的条件是（ ） A. p= NULL B. p→next= NULL C. p=h D. p→next= h 二．填充题： 1. 循环链表的主要优点是 。 2. 一个n*n的对称矩阵,如果以行列为主序存入内存,其容量为 。 3. 在双向循环链表中,在指针P所指的结点之后插入指针f所指的结点,其操作 为 。 4. 设有一个空栈,现输入序列为1，2，3，4，5经过push,push,pop,push,pop,push,pop, push后，输出序列为 。 5. 一个算法，如果不论问题规模大小运行所需时间都一样，则算法的时间 复杂度是 。 6. 数据结构有线性结构，树结构 和 等几种逻辑结构。 7. 顺序存储的队列如果不彩用循环方式，则会出现 问题。 2 8. 在一个长度为n的顺序表中插入一个元素，最少需要移动 个元素、最多 需要移动 个元素。 9. 一个数组长度为20，用于存放一个循环队列，则队列最多只有 个元素。 10. 设单链表中指针p指向结点A，若要删除A之后的结点（若存在），则需要修改 指针的操作为 。 11. 对于一个以顺序实现的循环队列Q[0……m-1],队首,队尾指针分别为f和r,队列 判空的条件是 。 12. 直接选择排序算法在最好情况下所做的交换元素的次数为 。 13. 具有64个结点的完全二叉树的深度为 。 14. 已知二叉树中叶子数为50,仅有一个孩子的结点数为30,则总结点数为 。 15. 运算符 动态分配一个对象。 16. VC++中预定义的两种流对象是 和 。 17. 限定符用其所长来声明只读变量。 18. 类的对象,可作为 类的对象处理。 19．三种成员访问说明符分别是 、 和 。 20. 无论对于顺序存储还是链接存储的栈和队列来说,进行插入或删除运算的 时间复杂度相同,均为 。 三. 判断题： 1．具有线性表关系的集合中，若a，b是集合中的任意两个元素， 则必有a 3．不论abt栈是用数组实现，还是用指针实现，pop(s)与push(x，s)的时间复杂度均为o(n)（ 4．表中的每一个元素都有前驱和后继元素（ ） 5．数据元素是数据的最小单元（ ） 6．在单链表中任何两个元素的存储位置都有固定的联系，因此可以从首结点进行查找 任何一个元素（ ） 7．因为算法和程序没有区别，所以在数据结构中二者是通用的（ ） 8．如果某数据结构的每一个元素都最多只有一个直接后继结点，则必为线性表（ ） 3 ） 9．一个有序的单链表采用折半查找法比顺序查找法效率高得多（ ） 10．一个图可以没有边，但不能没有顶点（ ） 11．进栈操作时，必须判断栈是否已满（ ） 12．快速排序法在最好的情况下的时间复杂度是否O (n) （ ） 13．进栈、出栈操作的时间复杂度是否O (n)（ ） 14．对于二叉排序树，根元素肯定是值最大的元素（ ） 15．只要是算法，肯定可以在有限的时间内完成（ ） 16．不论是线性表还是树，每一个结点的直接前驱结点最多只有一个（ ） 17．线性表的唯一存储形式就是链表（ ） 18．已知指针p指向链表L中的某结点，执行语句p = p→next不会删除该链表中的结点（ 19．在链队列中，即使不设置尾指针也能进行入队操作（ ） 20．对称矩阵的存储只需要存储一半的数据元素（ ） 四. 算法题（在空格上填入适当内容）： 1. 设有程序段： int sum (int n ) { int s=0； for (int i=1；i<=n；i++) {int p=1； for (int j=1；j<=i；j++) p=p*j； s=s+p； } return s； } 该程序段的算法功能是： 其时间复杂度为： 2. 链队列的初始化： void linkqueue：：iniqueue ( linkqueue &s ) { link *p； 4 ） p=new link； s．front= p； s．rear = p； } 3. 已知STACK表示栈的数据结构，push为将一个值为x的元素进栈，若成功返回1， 否则返回0： typedef struct { int data[100]； int tip； } STACK； int push ( STACK *s，int x) { if ( ) return 0； s→top ++； =x； return 1; } 4. 采用冒泡排序法对数组a进行排序： bsort (int a[ ]，int n ) { int n，j，i，tmp； for (i= ；i>=1；i--) { for (j=1；j>=i；j++) { if ( ) { tmp = a[j]； a[j]= a[j+1]； a[j+1]= tmp； 5 } } } } 5. 已知数组a有n个元素，并已由小到大排序，函数search的功能是采用折半查找法找值 为x的元素，并返回其下标，如查不到，返回-1: int search (elem a[ ]，int n，int x) { int i1，i2，k； i1=0；i2=n-1； while (i1<=i2) { k=(i1+i2)/2； if ( a[k]= =x) ； if ( x } return -1； } 6. 以下算法实现二叉树排序上的查找： bitreptr *bstsearch ( bitreptr *t，keytype k) { if (t==NULL) return NULL； else while (t!= NULL) { if (t→key==k ) ； if (t→key>k ) return ( bstsearch (t→lchild，k))； else ； } 6 } 7. 将双向循环链表进行逆置： void invert (dulink *head ) { dulink *p，*q； p=head； do { q=p→next； p→next= p→prior； ； p=q； } while ( ) } 8. 算法实现矩阵的相乘： void mat ( int a[m][n]，b[n][l]，c[m][l] ) { int i，j，k； for (i=0；i for (k=0；k 该算法的时间复杂度为： 7 因篇幅问题不能全部显示，请点此查看更多更全内容