第01题

当存储空间有足够的空闲空间时，在保持表内元素顺序相对不变的情况下，下列哪些操作会必然导致产生移动次数（ ）。 I. 表头插入一个元素II. 表头删除一个元素III. 表尾插入一个元素IV. 表尾删除一个元素

以下 C 代码的时间复杂度是（ ）。 int count = 0; for (int i=0; i*i<n; i++) for (int j=0; j<i; j++) count++;

已知带头结点的非空单链表 L 的头指针为 h，指针 p 指向 L 中间的一个链表结点（不是第一个和最后一个结点）。q=p->next，p->next=q->next，q->next=h->next，h->next=q。这段代码的功能是（）。

下列对顺序存储的有序表（长度为 n）实现给定操作的算法中平均时间复杂度为 O(1) 的是（ ）。

下列程序段的时间复杂度是（ ）。 int sum = 0; for (int i = 1; i < n; i *= 2) for (int j = 0; j < i; j++) sum++;

已知头指针 h 指向一个带头结点的非空单循环链表，结点结构为 其中 next 是指向直接后继结点的指针，p 是尾指针，q 是临时指针。现要删除该链表的第一个元素，正确的语句序列是（ ）。

将一个 10*10 对称矩阵 M 的上三角部分的元素 mi,j​(1≤i≤j≤10) ，按列优先存入 C 语言的一维数组 N 中，元素 m7,2​ 在 N 中的下标是（ ）

设 n 是描述问题规模的非负整数，下列程序段的时间复杂度是（ ）。 x = 0; while (n >= (x + 1) * (x + 1)) x = x + 1;

若栈 S1 中保存整数，栈 S2 中保存运算符，函数 F() 依次执行下述各步操作： 从 S1 中依次弹出两个操作数 a 和 b;从 S2 中弹出一个运算符 op;执行相应的运算 b op a;将运算结果压入 S1 。 假定 S1 中的操作数依次是 5,8,3,2（2 在栈顶），S2 中的运算符依次是 ×,−,+ （ + 在栈顶）。调用 3 次 F() 后，S1 栈顶保存的值是（ ）。

下列函数的时间复杂度是（ ）。 int func(int n) { int i = 0, sum = 0; while(sum < n) sum += ++i; return i; }

已知表头元素为 c 的单链表在内存中的存储状态如下表所示。现将 f 存放于 1014H 处并插入单链表，若 f 在逻辑上位于 a 和 e 之间，则 a,e,f 的 “链接地址” 依次是（ ）。

已知程序如下： int S(int n) { return (n <= 0) ? 0 : S(n - 1) + n; } void main() { cout << S(1); } 程序运行时使用栈来保存调用过程的信息，自栈底到栈顶保存的信息依次对应的是（ ）。

下列程序段的时间复杂度是（ ）。 count = 0; for (k = 1; k <= n; k *= 2) for (j = 1; j <= n; j++) count++;

已知两个长度分别为 m 和 n 的升序链表，若将它们合并为一个长度为 m+n 的降序链表，则最坏情况下的时间复杂度是（）。

求整数 n(n≥0) 阶乘的算法如下，其时间复杂度是（ ）。 int fact(int n) { if (n <= 1) return 1; return n * fact(n - 1); }

设 n 是描述问题规模的非负整数，下面程序片段的时间复杂度是（ ）。 x = 2; while (x < n / 2) x = 2 * x;

若元素 a, b, c, d, e, f 依次进栈，允许进栈、退栈操作交替进行，但不允许连续三次进行退栈操作，则不可能得到的出栈序列是（ ）。

为解决计算机与打印机之间速度不匹配的问题，通常设置一个打印数据缓冲区，主机将要输出的数据依次写入该缓冲区，而打印机则依次从该缓冲区中取出数据。该缓冲区的逻辑结构应该是（ ）。