出几道考研数据结构和C语言题目 木灵的炼金工作室

1 阅读以下程序:

struct test {
    int a;
    char b;
    short d;
    int c;
};

struct test2 {
    int a;
    char b;
    int c;
    short d;
};

在32位系统下,上述testtest2实例占用的空间是否相同?为什么?

解答:test结构体的内部内存分布为4,1,2,4,可以被分入三个4字节内存块中,因此test占用空间为12字节。
test2结构体的内部内存分布为4,1,4,2,由于需内部内存对齐的原因,它不能被对齐地放入三个4字节内存块,只能对齐地放入四个4字节内存块,因此test2占用空间是16字节。
上述的差异产生的问题不能被编译器在编译期和运行期优化。

2 简要回答

1 简单描述printf函数的传参机制:为什么printf可以接受任意数量的参数?
2 如printf使用了不匹配的格式化字符串,比如:在16位系统下,执行printf("%d", 0x12345678),会得到输出22136。试解释这样的现象。

解答:
1 printf使用变长参数类型,将任意数量的参数按位从后向前压入一个栈内,然后传给printf。printf在接收到参数时,首先提取位于栈顶的格式化串,再根据格式化串的占位符从栈中提取相应的位数,按照占位符形式对位作一定解释,后输出。
2 不妨以上述例子为例:首先,printf接收到传来的参数包,在栈顶发现字符串”%d”,提示它需要在栈中弹出”%d”相应的位数,而16位系统中的int是16位,因此它从栈中弹出16位。而因为之前提到在传参过程中,printf按位压栈,故弹出时从末尾开始(大端/小端机均一致),弹出的16位是0x8765,调整为正常顺序,按16位补码解释,为22136。

3 简要回答

我们在C语言头文件中经常会看到形如

#ifndef XXX
#define XXX
...
#endif

的内容,请问它的作用是?如果没有它,会可能导致什么错误?

解答: 它的作用是为了防止头文件被反复包含而产生的问题。如无它,编译器会在链接代码的过程中报出“xxx重复定义”的问题。

4 阅读以下程序

for(int i = 0; i < strlen(str); i++) {
    putchar(str[i]);
}

这样的程序有什么效率问题?编译器能否在编译期将其优化?

解答
这玩意每跑一次都要跑一个strlen遍历一遍字符串,时间$O(n^2)$。
不优化,编译器不会看循环体里有什么操作的。

5 阅读以下程序

sum(unsigned int n) {
    if (n) return n + sum(n - 1);
    else return 0;
}

这样的程序有何效率问题?编译器能否在编译期将其优化?

解答
尾递归,白白浪费$O(n)$的堆栈空间。
大部分编译器会优化尾递归为循环。

6 简要回答

尝试给出二分查找算法的$O(\log n)$时间界的求算过程

自己看书,必有。

7 简要回答

1 请给出一种判断链表是否有环的算法,并且要求:对于n长度的链表,空间复杂度为$O(1)$。
2.我们知道,最小生成树的「破圈算法」是持续找到图中的圈,并且将圈中各个边中权值最大者删除来找到最小生成树,直到没有圈为止。那么,如何在一个图中找到圈并且定位其包含的所有边?

解答
1 快慢双指针法,海淀小学生都会。
2 找圈无非就是使用BFS找自己到自己的最小路径。找到之后回溯路径即得到环。

8 简要回答

1 使用开放定址法的散列表如需删除元素,应怎么做?为什么?
2 双散列法(严蔚敏用语:再散列法)中的第二散列函数的值域能否包含0?为什么?

解答
1 只可用删除标记的形式懒惰删除。开放定址如发生冲突,其散列映射是依赖于冲突解决路径上的所有元素的。如只是简单地删掉,那么在它之后的所有同义元素均不能被正确寻址。
2 不能包含0。双散列法实际上就是高端版的线性探查法,第二散列函数实际是一个偏移量,当遇到冲突的时候使用它算出的散列值作偏移量向前移动插入点。如是0,则会一直在第一次的散列冲突位置死循环。这好吗?这不好。

9 简要回答

请给出由二叉树的前序和中序序列唯一确定一颗二叉树的算法。(自然语言、C\C++\Java)

解答
LeetCode题解,请。


Copyright AmachiInori 2017-2021. All Right Reserved.
Powered By Jekyll.
amachi.com.cn