In this paper, we attempt to automatically annotate the Penn Chinese Treebank with semantic dependency structure. Initially a small portion of the Penn Chinese Treebank was manually annotated with headword and semantic dependency relations. An initial investigation is then done using a Naive Bayesian Classifier and some handcrafted rules. The results show that the algorithms and proposed approach are effective at determining semantic dependency structure automatically. The Naive Bayesian Classifier makes a good baseline algorithm for future research.